减少找到N线交叉点的时间 [英] Reduce time taken to find N line intersection

问题描述

有 N 条线段，它们是水平或垂直的。现在，我需要找出相交的总数和每个线段的相交的总数。 N 最多可以为 100000 。我尝试检查每对线。答案是正确的，但是我需要减少它所花费的时间。

There are N line segments which are either Horizontal or vertical. Now I need to find out total number of Intersections and total number of Intersections per line segment. N can go upto 100000. I tried checking every pair of lines. The answer is correct but I need to reduce it's time taken by it.

这是我的代码：

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

有人可以帮助我减少此程序的时间复杂度吗？

Can someone help me out in reducing the time complexity of this program ?

推荐答案

这是O（n log n）时间算法，该算法使用带有Fenwick树的扫掠线。

Here's an O(n log n)-time algorithm that uses a sweep line with a Fenwick tree.

步骤0：重新映射坐标

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

Sort the x-coordinates and replace each value by an integer in 0..n-1 so as to preserve order. Do the same for y-coordinates. The intersection properties are preserved while allowing the algorithms below an easier implementation.

步骤1：平行线段

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

I'll describe this step for horizontal segments. Repeat for the vertical segments.

按y坐标对水平线段进行分组。一次处理一组，如下所示为扫掠线创建事件。每个段在其较小的端点处都有一个开始事件，在其较大的端点处有一个停止事件。如果要闭合的线段，则排序在停止之前开始。按排序顺序扫描事件，跟踪当前与扫描线相交的线段数以及已处理的开始事件数。一个路段的平行相交数为（在开始时间相交的路段数+在停止时间处处理的开始事件数-在开始时间处处理的开始事件数）。 （另请参见给出一组间隔，找到具有最大交点数的间隔，以获取我对此的先前解释。）

Group the horizontal segments by y coordinate. Process one group at a time, creating events for the sweep line as follows. Each segment gets a start event at its lesser endpoint and a stop event at its greater. Sort starts before stops if you want closed line segments. Sweep the events in sorted order, tracking the number of line segments that currently intersect the sweep line and the number of start events processed. The number of parallel intersections for a segment is (number of segments intersected at start time + number of start events processed at stop time - number of start events processed at start time). (See also Given a set of intervals, find the interval which has the maximum number of intersections for a previous explanation of mine for this.)

第2步：垂直线段

我将通过计算每个水平线段相交多少垂直线段来描述此步骤

I'll describe this step in terms of counting for each horizontal line segment how many vertical line segments it intersects.

我们执行另一种扫掠线算法。这些事件是水平线段起点，垂直线段和水平线段停止，并假设闭合线段以该顺序排序。对于每一个y坐标，我们使用一棵Fenwick树来追踪到目前为止，有多少垂直线段覆盖了该y坐标。要处理水平起点，请从其相交计数中减去其y坐标的树值。要处理水平停止，请将其y坐标的树值添加到其相交计数。这意味着计数增加了差异，差异是在活动状态下刺入水平段的垂直段的数量。要处理垂直线段，请使用Fenwick树的功能快速将其较小的y坐标与较大的y坐标（包括闭合线段）之间的所有值递增。

We do another sweep line algorithm. The events are horizontal segment starts, vertical segments, and horizontal segment stops, sorted in that order assuming closed line segments. We use a Fenwick tree to track, for each y coordinate, how many vertical segments have covered that y coordinate so far. To process a horizontal start, subtract the tree value for its y coordinate from its intersection count. To process a horizontal stop, add the tree value for its y coordinate to its intersection count. This means that the count increases by the difference, which is the number of vertical segments that stabbed the horizontal one while it was active. To process a vertical segment, use the power of the Fenwick tree to quickly increment all of the values between its lesser y coordinate and its greater (inclusive assuming closed segments).

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

If you want, these sweep line algorithms can be combined. I kept them separate for expository reasons.

这篇关于减少找到N线交叉点的时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！