在任意多边形中，如何检测任意边与另一边相交的自由度？
我正在为旅行商问题绘制一个多边形，并且想测试任何路径的不相交，作为自适应停止遗传搜索的一种方法。我尝试简单地检查线段或交点，但有时会得到不正确的结果，即使仍然存在一个或多个交点，也会终止搜索。
I am drawing a polygon for the Traveling Salesman problem, and would like to test for non-intersection of any paths, as a means of adaptively halting the genetic search. I tried simply checking line segments or intersection, but sometimes I get an incorrect result, terminating the search even though one or more intersections remain.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这个问题本质上相当于检测任意一组线段中的交点。
例如，可以使用bentley-ottmann算法来解决这个问题。当然，只要找到一个路口就可以终止。
简单的检查只会检查每条边与其他边（在多边形中不相邻，因为它们不能相交），但由于您只需要找到一个交集，因此输出敏感算法（像 Bentley-ottmann）可以大大加快您的检查速度。
This problem is essentially equivalent to detecting intersections in an arbitrary set of line-segments.
For example, the bentley-ottmann algorithm can be used to solve this problem. Of course, you can terminate as soon as you find one intersection.
A naive check would just check every edge versus every other edge (that is not adjacent in the polygon, because those cannot intersect), but since you just need to find one intersection, the output-sensitive algorithms (like bentley-ottmann) can speed up your check quite a lot.