检查Polygon是自相交 [英] Check if Polygon is Self-Intersecting

问题描述

我有System.Windows.Shapes.Polygon对象，其布局是完全由一系列点的确定。我需要确定此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²).

  稍快，中期内存占用（改性以上版本）：空间中的水桶的商店边，然后在每个桶基础上执行上述算法。复杂的为O（n ² / M）的的的 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)

  最后一个是我最喜欢的，因为它有良好的速度 - 内存平衡，尤其是宾利奥特曼算法 。实施是不是太复杂，无论是。

  The last is my favorite as it has good speed - memory balance, especially the Bentley-Ottmann algorithm. Implementation isn't too complicated either.

  这篇关于检查Polygon是自相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！