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,I,H },{G,H,I})

Answer 1

我找到了答案。

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

参考“如何检测两条线段相交的位置？ ”，计算给定线段的所有相交点。它是 O(n^2)，但可以通过使用空间树（例如 R-Tree、四叉树）升级到 O(n log n)。

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

参考“平面图中的小环求”，计算每个顶点的连接边角，并排序。完成后，通过“转向最左边”的策略遍历每条边并找到所有循环。

这将找到所有循环，但也会找到不需要的外部循环。外环是顺时针的，其他环都是逆时针的，所以用“如何判断多边形点列表是否顺时针？ ”中的方法去掉顺时针的环。