找到每个交点的线段和相交线段列表的交点

Question

我尝试使用CGAL从2D线段列表中找出“所有交点”和“每个交点的相交线段”。由于某些原因，我想使用Bentley-Ottmann算法。 CGAL库有一个叫做Sweepline 2的算法的C++实现，但是我只能找到交点。 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<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坐标。