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

Question

我有一个 System.Windows.Shapes.Polygon 对象，其布局完全由一系列点决定。我需要确定该多边形是否自相交，即多边形的任何边是否与其他边在非顶点的点相交。

有没有一种简单/快速的方法来计算这个？

Answer 1

检查任何一对不连续线段是否相交。

Answer 2

我是这里的新人，这个问题已经足够老了。然而，这里是我的 Java 代码，用于确定由有序点集定义的多边形的任何对边是否交叉。您可以删除用于调试的打印语句。我也没有包含返回找到的第一个交叉点的代码。我正在使用标准 java 库中的 Line2D 类。

/**
 * Checks if any two sides of a polygon cross-over.
 * If so, returns that Point.
 * 
 * The polygon is determined by the ordered sequence
 * of Points P 
 * 
 * If not returns null
 * 
 * @param V vertices of the Polygon
 * 
 * @return
 */
public static Point verify(Point[] V)
{
    if (V == null)
    {
        return null;
    }
    
    int len = V.length;
    
    /*
     * No cross-over if len < 4
     */
    if (len < 4)
    {
        return null;
    }
    
    System.out.printf("\nChecking %d Sided Polygon\n\n", len);
    
    for (int i = 0; i < len-1; i++)
    {
        for (int j = i+2; j < len; j++)
        {
            /*
             * Eliminate combinations already checked
             * or not valid
             */
            
            if ((i == 0) && ( j == (len-1)))
            {
                continue;
            }
            
            System.out.printf("\nChecking if Side %3d cuts Side %3d: ", i, j);
            
            boolean cut = Line2D.linesIntersect(
                    V[i].X,
                    V[i].Y,
                    V[i+1].X,
                    V[i+1].Y,
                    V[j].X,
                    V[j].Y,
                    V[(j+1) % len].X,
                    V[(j+1) % len].Y);
            
            if (cut)
            {
                System.out.printf("\nSide %3d CUTS Side %3d. Returning\n", i, j);
                return ( ... some point or the point of intersection....)
            }
            else
            {
                System.out.printf("NO\n");
            }
        }
    }
    
    return null;
}

Answer 3

为了完整起见，我在本次讨论中添加了另一个算法。

假设读者了解轴对齐边界框（如果不知道，请谷歌），使用“扫描和修剪算法”快速找到 AABB 冲突的边缘对可能非常有效。 （谷歌搜索）。然后对这些对调用交叉例程。

这里的优点是，您甚至可以与非直边（圆和样条线）相交，并且该方法更通用，尽管效率几乎相似。

Answer 4

• 简单、缓慢、内存占用低：将每个片段与所有其他片段进行比较并检查是否有交集。复杂度 O(n²)。

• 速度稍快，内存占用中等（上述的修改版本）：将边缘存储在空间“桶”中，然后在每个桶的基础上执行上述算法。 m 个存储桶的复杂度 O(n² / m)（假设均匀分布）。

• 快速&高内存占用：使用空间哈希函数将边分割到桶中。检查是否有碰撞。复杂度 O(n)。

• 快速&低内存占用：使用扫描线算法，例如 此处（或此处）。复杂度 O(n log n)

最后一个是我最喜欢的，因为它具有良好的速度 - 内存平衡，尤其是 Bentley-Ottmann 算法。实施也不太复杂。