求线段交点及每个交点的交点线段列表

Question

我试图使用CGAL从2D中的段列表中找出"所有交点"one_answers"每个交点的相交段"。出于某些原因，我想使用Bentley-Ottmann算法。CGAL库有一个称为swepline 2的算法的c++实现，但有了这个，我只能找到交叉点。在CGAL中是否存在其他实现?或者我如何解决这个问题?

Answer 1

Edit:真正快速的解决方法是使用Sweep line 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.
    }
}

现在要填充那个块，而不是重新发明任何东西，只需参考如何检测两条线段相交的位置?

如上一环节所示，计算r × s和(q−p) × r的值，其中x为向量叉积。从这里开始，如果您关心细节，只需使用if/else块来说明四种情况(ctrl f表示"现在有四种情况:")。如果你只是想要你在问题中概述的东西，只要检查情况3的有效性。如果它是有效的，将线段的索引以及x和y坐标存储在矢量/你正在使用的任何结构中。

您需要做的唯一额外的事情是使用compute u并将其应用于您正在检查的两条线段的第二条线段，以存储交点的xy坐标