减少寻找 N 线交点所需的时间

有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;
}

有人可以帮我降低这个程序的时间复杂度吗？

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

步骤0：坐标重映射

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

第一步：平行线段

我将针对水平段描述此步骤。对垂直线段重复上述步骤。

按 y 坐标对水平线段进行分组。一次处理一组，为扫描线创建事件，如下所示。每个段在其较小端点处获得一个开始事件，并在其较大端点处获得一个停止事件。如果您想要闭合线段，则在停止之前开始排序。按排序顺序扫描事件，跟踪当前与扫描线相交的线段数以及处理的启动事件数。线段的并行交叉数量为（开始时间交叉的线段数量 + 停止时间处理的开始事件数量 - 开始时间处理的开始事件数量）。 （也可以看看给定一组区间，找出交集数最多的区间 https://stackoverflow.com/questions/21966886/given-a-set-of-intervals-find-the-interval-which-has-the-maximum-number-of-inte/22017949#22017949我之前对此的解释。）

步骤2：垂直线段

我将通过计算每个水平线段与其相交的垂直线段的数量来描述此步骤。

我们做了另一种扫线算法。这些事件是水平线段开始、垂直线段和水平线段停止，假设闭合线段按该顺序排序。我们使用芬威克树来跟踪，对于每个 y 坐标，到目前为止有多少垂直线段覆盖了该 y 坐标。要处理水平起点，请从其交集计数中减去其 y 坐标的树值。要处理水平停靠点，请将其 y 坐标的树值添加到其交叉点计数中。这意味着计数会增加差值，即在水平段处于活动状态时刺入水平段的垂直段的数量。要处理垂直线段，请使用 Fenwick 树的功能快速递增其较小 y 坐标和较大 y 坐标（包括假设闭合线段）之间的所有值。

如果需要，可以组合这些扫描线算法。出于说明的原因，我将它们分开。