c++ - 查找线段的交点和每个交点的相交线段列表

Question

我正在尝试使用 CGAL 从二维线段列表中找出“所有交点”和“每个交点的相交线段”。出于某些原因，我想使用 Bentley–Ottmann 算法。 CGAL 库有此算法的 c++ 实现，称为 Sweepline 2但有了这个我只能找到交点。 CGAL 中是否还有其他实现？或者我该如何解决这个问题？

Answer 1

编辑:真正快速的解决方法是使用扫描线 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 ，这样您就可以存储所有不同的交集。

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

现在填写该 block ，而不是重新发明任何东西，只需引用 How do you detect where two line segments intersect? .

如上链接所示，计算 r × s 和 (q − p) × r 的值，其中 × 是 vector 叉积。从那里开始，如果您关心细节，只需使用 if/else block 来说明四种情况(ctrl f 表示“现在有四种情况:”)。如果您只想要问题中概述的内容，只需检查案例 3 的有效性。如果有效，请将线段的索引以及 x 和 y 坐标存储在 vector/您正在使用的任何结构中.

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