Search code examples
mathgeometrytriangular

How to detect all regions that are surrounded by n line segments?

When you draw 3 line segments in a 2-dimensional plane, it might compose a triangle.

How can I find all polygons that are produced by n line segments? Are there any efficient algorithms I can use?

Input: first and last point coordinate for each line segments (Ex. Points A=(x_A,y_A), B=(x_B,y_B), ... , I=(x_I,y_I))

lines

Output: All produced polygons and producing line sets (Ex. {A,B,C,F},{A,C,E,F,H},{E,F,I},{E,F,I,H},{G,H,I})

polygons produced by given lines

Solution

  • I found the answer.

    Step 1. Calculate all intersecting points for each line segments.

    Referring "How do you detect where two line segments intersect?", calculate all intersecting points for the given line segments. It's O(n^2), but can be upgraded to O(n log n) by using spatial trees (ex. R-Tree, Quad trees).

    enter image description here

    Step 2. Find all couter-clockwise loops.

    Referring "small cycle finding in a planar graph", Calculate the connecting edge angle for each vertex, and sort it. After it's done, traverse every edges and find all loops by "turning to the most-left-edge" strategy.

    This will find all loops, but will also find an outer loop that's not needed. The outer loop is clockwise, compared to other loops that are all counter-clockwise, so remove the clockwise loop by using method written in "How to determine if a list of polygon points are in clockwise order?".

    enter image description here