减少查找N条线段相交所需的时间

Question

有 N 条直线段，它们要么是水平的，要么是垂直的。现在我需要找出总交点数和每条直线段的交点数。N 可以多达 100000。我试图检查每一对直线。答案是正确的，但我需要缩短计算时间。

这是我的代码：

using namespace std;

typedef struct Point
{
     long long int x;
     long long int y;
} ;


bool fun(Point p0, Point p1, Point p2, Point p3)
{
    double s1_x, s1_y, s2_x, s2_y;
    s1_x = p1.x - p0.x;     s1_y = p1.y - p0.y;
    s2_x = p3.x - p2.x;     s2_y = p3.y - p2.y;

    double s, t;
    s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        return 1; // Collision detected
    }

    return 0; // No collision
}


int main()
{
     long long int n // number of line segments;

     Point p[n],q[n]; // to store end points of line segments

    for( long long int i=0;i<n;i++)
    {

// line segments is defined by 2 points P(x1,y1) and Q(x2,y2)
        p[i].x=x1;
        p[i].y=y1;
        q[i].x=x2;
        q[i].y=y2;
    }

    for( long long int i=0;i<n-1;i++)
    {
        for( long long int j=i+1;j<n;j++)
        {
            if(fun(p[i],q[i],p[j],q[j]))
               count++;
        }

    }

    return 0;
}

有人能帮我减少这个程序的时间复杂度吗？

- sammy

---

如果它们是水平或垂直的，则检查交叉点要比任意线（如您的方法）容易得多。此外，首先按x/y坐标对线进行排序。然后您就知道可能的交叉点在哪个区域。更复杂的方法是使用线段树或区间树。 - Nico Schertler

同一个老师还是同一个比赛？http://stackoverflow.com/questions/40570886/c-modified-line-segment-intersection - MBo

请查看以下内容：使用C#实现Hoey Shamos算法，其中包含两个答案... - Spektre

@MBoI我不认识他，但问题看起来相似，不过我们的解决方法非常不同。 - sammy

@Spektre 谢谢您的帮助。 - sammy

Answer 1

这是一个使用带有 Fenwick 树的扫描线的 O(n log n) 时间复杂度算法。

步骤 0：坐标重映射

按 x 坐标排序，并替换每个值为 0..n-1 中的整数，以保持顺序。对 y 坐标执行相同操作。保留交集属性，同时允许以下算法更容易实现。

步骤 1：平行线段

我将描述水平线段的此步骤。垂直线段请重复此操作。

通过 y 坐标对水平线段进行分组。逐个处理一组，为扫描线创建以下事件。每个线段在其较小端点处获得起始事件，在其较大端点处获得停止事件。如果要关闭线段，则按开始时间排序。按排序顺序扫描事件，跟踪当前与扫描线相交的线段数量和已处理的起始事件数量。线段的平行交点数为（开始时间相交的线段数 + 在停止时间处理的起始事件数 - 在开始时间处理的起始事件数）。（另请参见我先前关于此问题的解释：Given a set of intervals, find the interval which has the maximum number of intersections）

步骤 2：垂直线段

我将描述每个水平线段与其相交的垂直线段的计数。

我们执行另一个扫描线算法。事件是水平线段开始、垂直线段和水平线段停止，按照这个顺序排序，假设线段是封闭的。我们使用 Fenwick 树来跟踪每个 y 坐标已经有多少垂直线段覆盖了它。要处理水平线段的开始，从其交点计数中减去其 y 坐标的树值。要处理水平结束，请将其 y 坐标的树值添加到其相交计数中。这意味着计数增加了差值，即在活动时刺穿水平线段的垂直线段数量。要处理垂直线段，请使用 Fenwick 树的功能快速递增其较小 y 坐标和较大 y 坐标之间（包括封闭线段）的所有值。

如果您愿意，可以合并这些扫描线算法。出于说明原因，我将它们分开。

- David Eisenstat