algorithm - 从多段线中去除环路的高效算法

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)。我知道我可以做得比这更好，例如使用 set of all intersecting line segments常规作为起点。但是，鉴于已经订购了积分，我认为我应该可以做得更好。请注意，上面的版本可以正常工作，并返回剩余点数，这很方便，但不是必需的。

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

Answer 1

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

算法的瓶颈是排序，可以在O(nlogn) 中完成。我很确定您不能比 nlog n 做得更好，因为这些类型的问题通常可以归结为排序。您或许可以将此问题简化为找到一组点的凸包，这在小于 n log n 的情况下也是不可能的。