math - 如何检测所有被n条线段包围的区域？

Question

当你在二维平面上绘制3条线段时，它可能会组成一个三角形。

如何找到由 n 条线段生成的所有多边形？我可以使用任何有效的算法吗？

输入:每个线段的第一个和最后一个点坐标(例如点 A=(x_A,y_A), B=(x_B,y_B), ... , I=(x_I,y_I))

输出:所有生成的多边形和生成的线集(例如。{A,B,C,F},{A,C,E,F,H},{E,F,I},{E,F,我,H},{G,H,我})

Answer 1

我找到了答案。

第 1 步。计算每条线段的所有交点。

引用“How do you detect where two line segments intersect?”，计算给定线段的所有交点。它是 O(n^2)，但可以通过使用空间树(例如 R-Tree、四叉树)升级到 O(n log n)。

第 2 步。找到所有逆时针循环。

引用“small cycle finding in a planar graph”，计算每个顶点的连接边角度，并排序。完成后，遍历每条边，通过“转向最左边”策略找到所有环。

这会找到所有循环，但也会找到不需要的外部循环。外层循环是顺时针的，其他循环都是逆时针的，所以用“How to determine if a list of polygon points are in clockwise order?”中写的方法去掉顺时针循环。