有没有简便快速的方法来检查多边形是否自相交? [英] Is there an easy and fast way of checking if a polygon is self-intersecting?
问题描述
我有一个System.Windows.Shapes.Polygon
对象,其布局完全由一系列点确定.我需要确定该多边形是否是自相交的,即,该多边形的任意边在非顶点处是否与其他任意边相交.
I have a System.Windows.Shapes.Polygon
object, whose layout is determined completely by a series of points. I need to determine if this polygon is self-intersecting, i.e., if any of the sides of the polygon intersect any of the other sides at a point which is not a vertex.
是否有一种简便/快速的方法来计算?
Is there an easy/fast way to compute this?
推荐答案
-
轻松,缓慢,低内存占用:将每个线段与所有其他线段进行比较,并检查交叉点.复杂度 O(n 2 ).
Easy, slow, low memory footprint: compare each segment against all others and check for intersections. Complexity O(n2).
速度稍快,内存占用量中等(上述版本):将边缘存储在空间存储桶"中,然后在每个存储桶的基础上执行上述算法. m 桶的复杂度 O(n 2 /m)(假设分布均匀).
Slightly faster, medium memory footprint (modified version of above): store edges in spatial "buckets", then perform above algorithm on per-bucket basis. Complexity O(n2 / m) for m buckets (assuming uniform distribution).
快速&内存占用量大:使用空间哈希函数将边缘分成多个存储桶.检查碰撞.复杂度 O(n).
Fast & high memory footprint: use a spatial hash function to split edges into buckets. Check for collisions. Complexity O(n).
快速&低内存占用量:使用扫描线算法,例如这里).复杂度 O(n log n)
Fast & low memory footprint: use a sweep-line algorithm, such as the one described here (or here). Complexity O(n log n)
最后一个是我最喜欢的,因为它具有良好的速度-内存平衡,尤其是 Bentley-Ottmann算法 .实现也不太复杂.
The last is my favorite as it has good speed - memory balance, especially the Bentley-Ottmann algorithm. Implementation isn't too complicated either.
这篇关于有没有简便快速的方法来检查多边形是否自相交?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!