是否有一种简单快捷的方法来检查多边形是否自相交?

问题描述

我有一个 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²).

  • Easy, slow, low memory footprint: compare each segment against all others and check for intersections. Complexity O(n²).

    稍快，中等内存占用(上面的修改版本):将边缘存储在空间桶"中，然后在每个桶的基础上执行上述算法.m 个桶的复杂度 O(n²/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(n² / 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.

    这篇关于是否有一种简单快捷的方法来检查多边形是否自相交?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！

    The End

    ---