7

I have a polyline, given as an ordered set of (X,Y) coordinates, that may cross over itself to form one or more loops. From this, I want to extract a polygon that has the loops removed, which will include the intersection points where the line crosses 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've made a few optimizations to the above, e.g. by counting cumulative angle between successive line segments we know we can't have hit an intersection until we've gone through 360 degrees, the algorithm remains a pretty terrible O(n^2). I know I can do much better than this, e.g. using a set of all intersecting line segments routine as a starting point. Given that the points are already ordered however, I reckon I should be able do better. Note that the above version works in place, and returns the number of remaining points, which is handy but not a requirement.

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

SmacL
  • 22,555
  • 12
  • 95
  • 149
  • 1
    Hmm, the points are nor really ordered though. Yes, they're ordered so that two successive points form a line segment, but these line segments may very well look like a plate of tangled spaghetti, right? I don't think such an ordering will help you much. Also see this previous Q&A: http://stackoverflow.com/questions/8119403/algorithm-to-find-intersections-between-polylines which looks to be a duplicate. – Bart Kiers Nov 22 '11 at 09:39
  • 1
    It's certainly a close question, but I'm looking for intersections within a single polyline, rather than intersections between a set of polylines, which is slightly different. Outside of counting the cumulative angle, the order could well be a red herring. – SmacL Nov 22 '11 at 09:49
  • ah, yes, your question is indeed different. Although my guess is that the solution to both questions are the same... Interesting question. – Bart Kiers Nov 22 '11 at 09:51

2 Answers2

0

Try to use a sweep line algorithm approach. Intuitively, it's best to think of the algorithm graphically. You place the points in the plane and "sweep" over them from left to right. While sweeping, you maintain an invariant on the state of the lines you have already discovered. If there is an intersection between two lines it must happen between two lines we have already "discovered". Technically, you don't have to "sweep" the plane: you can check the invariant every time you stumble upon a point. So you can order the points by their x coordinate and go over them one by one.

The bottleneck of the algorithm is the sorting which can be done in O(nlogn). I'm pretty sure you can't do better than nlog n because these type of problems usually are reducible to sorting. You can probably reduce this problem to finding a convex hull of a set of points that is also not possible in less than n log n.

Guy
  • 14,178
  • 27
  • 67
  • 88
  • 2
    Err, Shane already mentioned that he can solve it in `O(n*log(n))` and linked to a page that lists a couple of sweep-line algorithms... – Bart Kiers Nov 22 '11 at 10:02
0

The usual assumptions that result in a speedup or a nicer algorithm are when the polygonal chain is either simple or convex. At the outset, your chain is neither.

There might be an incremental data structure that can do O(log n + s) line–simple polygonal chain intersection tests, but I suspect that even if it exists, it's more complicated and probably slower than just doing segment intersection.

Per
  • 2,594
  • 12
  • 18
  • I feel the ordering could help, insofar that I know as a minimum any two successive line segments (e.g. line segments that share a common point) do not otherwise intersect. Similarly you can say that for any sub-chain, where the accumulated change in direction between the first segment and current segment is less than 360 degrees, there is no intersection (within that sub-chain). I suspect that these pieces of information can be used to produce a more efficient algorithm than an 'all intersections' approach. – SmacL Dec 08 '11 at 12:17