Search code examples
c++rgeometrylinear-algebracomputational-geometry

Polygon Detection from a Set of Lines?

I have a set of connected, intersecting line segments. I want to detect all polygons that result from the intersection of these line segments, as follows:

Picture

I found a paper that presents an algorithm for solving this problem, but I'm not really a computer science person so I wasn't able to understand it. Here's a link to the paper. At this moment, my plan is to 1) find all intersections, and 2) somehow use these intersections to identify the polygons. I'm able to solve (1) through brute force, but (2) is a bit trickier. I'd prefer a solution in R or C++, but any language will do.

Solution

  • Assuming you have your line segments always as a closed polygonal chain and you have them in some sort of edge list. And, as you said, you have the intersection points already computed (brute force means O(n^2) time, in this case that is optimal as the line segments can intersect n^2 times).

    You can insert your intersection points from (1) into this list splitting the intersecting line segments, mark them as intersection points and reference to all intersecting line segments in this point. Furthermore, on every line segment two polygons are incident, thus add respective reference fields to every edge. Then just take the leftmost vertex in you input and walk along the edge list. Add to every edge that is traversed a reference to its left incident polygon (in this case) polygon number one. If you reach an intersection point, put it on some sort of stack for later recovery. Now analyse that point and continue walking on the leftmost path (between the line segment on which you reached the intersection point and all outgoing segments). At some point you reach your starting point and you have the first simple polygon closed.

    Now take the first intersection point from the stack. There must be an even number of line segments that start/end there. Find a line segment that has at most one incident polygon referenced (yet) and use it as as starting segment for polygon number two. You can walk along its chain in the same manner as before. (If you reference a line segment`s right incident polygon, take the rightmost turn on an intersection point.) When your stack ist empty your are done.

    Edit: After I looked one more time for a solution I found this implementation from Dan Sunday. I assume that is more useful as it is also already implemented.