找到每个交点的线段和相交线段列表的交点
问题描述:
我尝试使用CGAL从2D线段列表中找出“所有交点”和“每个交点的相交线段”。由于某些原因,我想使用Bentley-Ottmann算法。 CGAL库有一个叫做Sweepline 2的算法的C++实现,但是我只能找到交点。 CGAL中是否存在其他实现?或者我该如何解决这个问题?找到每个交点的线段和相交线段列表的交点
答
编辑: 真正快速修复也只是用扫描线2,遍历所有产生交叉点生成所有交叉点,并为每个交叉点记录这两个点的坐标,并包含所有线段指向你选择的结构。
一个快速的解决方案(虽然不是最有效的)是:
//Probably start off with a struct to store your information
struct intersection{
//This stores the x and y position of the intersection.
int[2] xyCoords;
//This stores the segment ids or indexes of the intersection line segments.
//For example, if the 1st and 5th line segment intersect, you would store 1 and 5 in here.
int[2] segmentIDs;
}
然后,只需创建相交结构的载体,所以你可以将所有不同的路口。
vector<intersection> intersectionVector;
然后,只需通过你在类似下面的东西有线段的循环:
for (int i = 0; i < numSegments; i++){
for (int j = 0; j < numSegments; j++){
//Don't look at the same points.
if (i == j)
continue;
//See below for pseudocode for this part.
}
}
我们填补该块,而不是重塑任何东西只是参考How do you detect where two line segments intersect?。
如上述链接所示,计算r×s和(q-p)×r的值,其中x是向量叉积。从那里,只要使用if/else块来解释这四种情况(如果你关心细节,请按Ctrl +“现在有四种情况:”)。如果你只是想要你在问题中概述的内容,只需检查第三种情况的有效性。如果它是有效的,则存储线段的索引以及矢量/结构中的x和y坐标。
您需要做的唯一一件额外的事情就是使用calculate u并将其应用到您正在检查的两个线段中,以便存储交叉点的x y坐标。