当你在二维平面上绘制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,我})
最佳答案
我找到了答案。
第 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?”中写的方法去掉顺时针循环。
关于math - 如何检测所有被n条线段包围的区域?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35456877/