高效算法：从折线中移除环路

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)或更好的算法？

- SmacL

---

嗯，这些点并没有真正被排序。是的，它们被排序成两个相邻的点形成一条线段，但这些线段可能看起来像一盘缠在一起的意大利面，对吧？我不认为这样的排序会对你有所帮助。另请参阅此前的问答：https://dev59.com/OV3Ua4cB1Zd3GeqP-TRb，这似乎是一个重复的问题。 - Bart Kiers

这确实是一个棘手的问题，但我正在寻找单个折线内的交点，而不是一组折线之间的交点，这略有不同。除了计算累积角度外，顺序可能是一个红鲱鱼。 - SmacL

啊，是的，你的问题确实不同。虽然我猜想两个问题的解决方案可能是相同的...有趣的问题。 - Bart Kiers

Answer 1

通常导致加速或更好算法的假设是多边形链要么是简单的，要么是凸的。但是在开始时，您的链既不简单也不凸。

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

- Per

---

我认为排序可以帮助，因为我至少知道任何两个连续的线段（例如共享公共点的线段）不会相交。同样，对于任何子链，如果第一个线段和当前线段之间的累积方向变化小于360度，则没有交点（在该子链中）。我怀疑这些信息可以用来产生比“所有交点”方法更有效的算法。 - SmacL

Answer 2

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

算法的瓶颈是排序，可以在O(nlogn)中完成。我非常确定您无法做得比nlog n更好，因为这些类型的问题通常可以归约为排序。您可能可以将此问题简化为查找一组点的凸包，但也不可能少于n log n。

- Guy

---

错误，Shane已经提到他可以用O(n*log(n))解决它，并链接到一个列出几个扫描线算法的页面... - Bart Kiers