有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坐标执行相同的操作。在保留交集属性的同时,允许下面的算法更容易实现。
步骤1:平行线段
我将针对水平线段描述此步骤。对垂直线段重复上述步骤。
通过y坐标对水平线段进行分组。一次处理一组,如下所示为扫掠线创建事件。每个段在其较小的端点处都有一个开始事件,在其较大的端点处有一个停止事件。如果要闭合的线段,则排序在停止之前开始。按排序顺序扫描事件,跟踪当前与扫描线相交的线段数量以及已处理的开始事件的数量。一个路段的平行相交数为(在开始时间相交的路段数+在停止时间处处理的开始事件数-在开始时间处处理的开始事件数)。 (有关此内容,我的先前解释也请参见Given a set of intervals, find the interval which has the maximum number of intersections。)
步骤2:垂直线段
我将通过计算每个水平线段相交多少垂直线段来描述此步骤。
我们执行另一种扫掠线算法。这些事件是水平线段起点,垂直线段和水平线段停止,并假设闭合线段以该顺序排序。对于每一个y坐标,我们使用一棵Fenwick树来跟踪到目前为止,有多少垂直线段覆盖了该y坐标。要处理水平起点,请从其相交计数中减去其y坐标的树值。要处理水平停靠点,请将其y坐标的树值添加到其相交计数。这意味着计数增加了差值,该差值是在激活事件段时刺穿水平段的垂直段的数量。要处理垂直线段,请使用Fenwick树的功能来快速递增其较小的y坐标与较大的y坐标之间的所有值(包括闭合线段在内)。
如果需要,可以组合使用这些扫掠线算法。出于说明原因,我将它们分开。
关于c++ - 减少查找N线相交所需的时间,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/40566994/