Bentley-Ottmann算法的推广

Question

本题涉及的是Bentley-Ottmann算法，该算法用于确定线段列表的交点。但正如维基百科中所述，它存在一些缺陷：

该算法假设线段不是垂直的，线段端点不位于其他线段上，交叉点由仅两条线段形成，并且没有两个事件点具有相同的x坐标。然而，这些一般位置假设对于大多数线段交点应用程序来说并不合理。

我的问题是，是否有一种通用化的算法可以克服/解决上述困难？

- Graviton

---

我认为你可以通过修改 Bentley-Ottmann 算法来处理所有这些特殊情况。但是你会失去算法的很多简单性。 - Keegan Carruthers-Smith

Answer 1

您所提供的维基百科文章有一节关于处理这些特殊情况的算法修改建议，其中建议对基本算法进行以下修改：

• 按照惯例，一个点在垂直于它的点上方时被认为在它的“左侧”；因此，垂直线的“左侧”端点是它的下端点。
• 事件可能由两条或更多条线的交叉组成。
• 到达事件点后，必须反转扫描线中与之相关的线段（不仅仅是交换，因为可能不止两个）。
• 处理完交叉后，可能需要删除两个以上旧事件点或插入两个以上新事件点。

- Gareth Rees

Answer 2

这些是Skanthak提出的算法修改（此处）：。

The algorithm proceeds as follows: It first creates events for all start- and endpoints of input segments. It then handles all events in sorted order.
 For each event, it fetches the associated list L of segments starting at that point and finds and removes all segments in the search tree that intersect the current event point. It reports all those segments as intersections in that point. It then switches the order of the comparison function by changing the flag to be slightly after the current event. It reinserts all previously removed segments that do not have their endpoint at the current event point (because they have to be removed from the structure at this point anyways) and additionally insert the segments from L (that are starting at this point). It checks the top and bottom neighbors above and below the current event point for new intersections and adds them as event points if it finds any.
 This way the algorithm is robust against all kinds of degeneracies, including vertical segments and overlapping segments, as well as segments intersecting on their endpoints.

for all segments s do
  Create events for the endpoints of s
end for
while event queue not empty do
  Remove the smallest event point p from the queue
  Let L be the set of segments that start at p
  I ← all segments in the sweep line structure that contain p
  remove I from sweep line structure
  if |L| + |I| ≥ 2 then
     Report intersections of L ∪ I
  end if
  C ← {s ∈ I | p is not endpoint of s}
  Insert C in sweep line structure in reversed order
  Check for new intersections among segments above and below p
end while

- Dr. belisarius