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

Question

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

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

Answer 1

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

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

• 快速&amp；高内存占用：使用空间散列函数将边缘分割成桶状。检查是否有碰撞。复杂度：使用空间哈希函数分割边缘，检查碰撞。O(n).

• 快速和amp; 低内存占用扫线算法：使用扫线算法，如所述算法。此处 (或 此处). 复杂度 O(n log n)

最后一个是我最喜欢的，因为它有很好的速度--内存平衡，特别是它有很好的速度。本特利-奥特曼算法. 实现也不复杂。

Answer 2

检查是否有任何一对 非相邻 线段相交。

Answer 3

为了完整起见，我在这个讨论中加入另一种算法。

假设读者知道轴对齐的边界框(如果不知道就谷歌一下)，使用 "Sweep and Prune Algorithm "可以非常有效地快速找到有其AABB的冲突的边对。(谷歌一下)。然后在这些边对上调用交集例程。

这里的优点是，您甚至可以与非直线边缘（圆和花键）相交，而且这种方法更通用，尽管几乎同样有效。

Answer 4

我是一个新来的小蜜蜂，这个问题已经很老了。然而，这里是我的Java代码，用于确定由一组有序点定义的多边形的任何一对边是否交叉。你可以去掉用于调试的print语句。我也没有包括返回找到的第一个交叉点的代码。

/**
 * 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;
}