Effective algorithm for removing loops from polylines

Question

I have a polyline defined as an ordered set of coordinates (X, Y) that can intersect itself to form one or more loops. From this I want to extract a polygon in which loops are removed that will include the intersection points where the line intersects itself. I currently have a crude brute force algorithm that works as follows:

int RemoveLoops(CoordType Points[],int NoPoints) { int n = 0; // Start of first line segment int m = 2; // Offset to n of second line segment int p = NoPoints; while (n + m + 1 < p) { CoordType Ip; // Intersection point if (Intersect(Points[n],Points[n+1],Points[n+m],Points[n+m+1],Ip))) { Points[n+1] = Ip; int d = m - 1; // Number of points to delete for (int i = n + m + 1; i < p; i++) Points[i - d] = Points[i]; p -= d; m = 2; continue; // Restart from intersection point } m ++; if (n + m + 1 >= p) // Reached end of line, change starting segment { m = 2; // Reset offset n++; // Increment starting segment } } return(p); // Return the number of points in the new poly line } 

While I made several optimizations for the above, for example, counting the cumulative angle between consecutive line segments, we know that we cannot get to the intersection until we go 360 degrees, the algorithm remains pretty terrible O (n ^ 2). I know that I can do much better than this, for example. using the set of all intersecting line segments as a starting point. Given that the items have already been ordered, I suppose I should be able to do better. Please note that the above version works and returns the number of points remaining, which is convenient, but not necessary.

Any ideas on a good algorithm for the above, O (n log n) or better?

Answer 1

Try using a line sweep algorithm . Intuitively, it is best to think about the algorithm graphically. You place the points in the plane and “sweep” them from left to right. When sweeping, you save an invariant about the state of the lines that you have already found. If there is an intersection between two lines, this should happen between two lines that we have already "discovered". Technically, you don’t need to “sweep” the plane: you can check the invariant every time you come across a point. Thus, you can order points by their x coordinate and iterate over them in turn.

The bottleneck of the algorithm is sorting, which can be done in O(nlogn) . I am sure that you cannot do better than nlog n , because these types of problems usually come down to sorting. You can probably reduce this problem to finding the convex hull of a set of points, which is also impossible less than n log n .

Answer 2

Common assumptions leading to an acceleration or a more pleasant algorithm are when the polygonal chain is either simple or convex. From the very beginning, your chain is not.

There may be an incremental data structure that can perform O (log n + s) tests for simple intersection of a polygonal line chain, but I suspect that even if it exists, it is more complex and probably slower than just intersecting segments.