从折线中去除环的有效算法

Question

我有一条折线，以一组有序的 (X,Y) 坐标给出，它可能会交叉自身以形成一个或多个循环。由此，我想提取一个已删除循环的多边形，其中将包括线与自身相交的交点。我目前有一个粗略的暴力算法，其工作原理如下；

int RemoveLoops(CoordType Points[],int NoPoints)
{
    int n = 0;  // Start of first line segment
    int m = 2;  // Offset to n of second line segment
    int p = NoPoints;
    while (n + m + 1 < p)
    {
        CoordType Ip; // Intersection point
        if (Intersect(Points[n],Points[n+1],Points[n+m],Points[n+m+1],Ip))) 
        {
            Points[n+1] = Ip;
            int d = m - 1;  // Number of points to delete
            for (int i = n + m + 1; i < p; i++)
                Points[i - d] = Points[i];
            p -= d;
            m = 2;
            continue;   // Restart from intersection point 
        }
        m ++;
        if (n + m + 1 >= p) // Reached end of line, change starting segment
        {
            m = 2;  // Reset offset
            n++;    // Increment starting segment
        }
    }
    return(p);  // Return the number of points in the new poly line
}

虽然我对上面的内容做了一些优化，例如通过计算连续线段之间的累积角度，我们知道在经过 360 度之前我们不可能遇到交叉点，但该算法仍然是一个非常糟糕的 O(n^ 2）。我知道我可以做得更好，例如使用 所有相交线段的集合 例程作为起点。然而，鉴于积分已经排序，我认为我应该能够做得更好。请注意，上面的版本可以正常工作，并返回剩余点数，这很方便，但不是必需的。

对于上述问题有什么好的算法吗，O(n log n) 或更好？

Answer 1

尝试使用扫描线算法方法。直观上，最好以图形方式思考该算法。您将这些点放置在平面上并从左到右“扫过”它们。在扫描时，您可以保持已发现的线的状态不变。如果两条线之间存在交点，那么它一定发生在我们已经“发现”的两条线之间。从技术上讲，您不必“扫描”平面：每次偶然发现一个点时，您都​​可以检查不变量。因此，您可以按点的 x 坐标对它们进行排序，并逐一检查它们。

该算法的瓶颈是排序，其时间复杂度为O(nlogn)。我很确定你不能比 nlog n 做得更好，因为这些类型的问题通常可以简化为排序。您可以将这个问题简化为找到一组点的凸包，这在小于 n log n 的情况下也是不可能的。

Answer 2

导致加速或更好算法的通常假设是当多边形链是简单的或凸的时。一开始，你的链条两者都不是。

可能有一个增量数据结构可以进行 O(log n + s) 行——简单的多边形链相交测试，但我怀疑即使它存在，它也比仅仅进行线段相交更复杂并且可能更慢。