从多义线删除循环的高效算法

我有一个折线，作为（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）或更好的算法的任何想法？

来源

2011-11-22 Shane MacLaughlin

嗯，点虽然也没有真正的有序。是的，他们的顺序是连续两个点形成一条线段，但这些线段很可能看起来像一盘混乱的意大利面，对吗？我不认为这样的排序会对你有很大的帮助。另请参阅此前的问答：http://stackoverflow.com/questions/8119403/algorithm-to-find-intersections-between-polylines看起来是重复的。 –

这当然是一个密切的问题，但我正在寻找单个多段线内的交点，而不是一组多段线之间的交点，这与稍有不同。在计算累积角度之外，顺序很可能是红鲱鱼。 –

啊，是的，你的问题确实不同。虽然我的猜测是这两个问题的解决方案都是一样的......有趣的问题。 –

尝试使用sweep line algorithm方法。直观地说，最好以图形方式考虑算法。你把这些点放在飞机上，从左到右“扫过”它们。在扫描时，您保持对已发现线条的状态不变。如果两条线之间有交点，它必须发生在我们已经“发现”的两条线之间。从技术上讲，你不必“扫掠”飞机：每当你偶然发现一个点时，你可以检查不变量。所以你可以通过他们的x坐标来排序这些点，然后逐个查看它们。

算法的瓶颈是可以在O(nlogn)中完成的排序。我很确定你不能比nlog n做得更好，因为这些类型的问题通常可以归结为排序。你可以减少这个问题，找到一组点的凸包，这在小于n log n的范围内也是不可能的。

来源

2011-11-22 09:56:31 Guy

Err，Shane已经提到他可以在'O（n * log（n））中解决它并链接到一个列出几条扫描线算法的页面...... –

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

可能会有一个增量数据结构可以执行O（log n + s）行 - 简单多边形链交集测试，但我怀疑即使它存在，它也会比执行段交集更复杂并且可能更慢。

来源

2011-11-22 14:23:37 Per

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

从多义线删除循环的高效算法

回答

相关问题