Bentley-Ottmann算法的推广

Question

Bentley-Ottmann算法用于确定线列表的交叉点.然而,如Wiki中所述,存在一些缺点:

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

我的问题是,这种算法有一个概括可以克服/克服上述困难吗？

Answer 1

您链接的维基百科文章有一个关于处理这些特殊位置的部分,它建议对基本算法进行这些修改:

• 按照惯例,一个点是垂直在其上方的点的"左"; 因此,垂直线的"左"端点是其下端点.
• 事件可能包括两条或更多条线的交叉点.
• 当达到事件点时,其事件段必须在扫描线中反转(不仅仅是交换,因为可能有两个以上).
• 处理完交叉后,可能会删除两个以上的旧事件点或要插入两个以上的新事件点.

Answer 2

以下是Skanthak提出的算法修改:.

该算法如下进行:它首先为输入段的所有起点和终点创建事件.然后它按排序顺序处理所有事件.
 对于每个事件,它从该点开始提取相关的段L列表,并查找并删除搜索树中与当前事件点相交的所有段.它将所有这些段报告为该点的交叉点.然后通过在当前事件之后稍微改变fl ag来切换比较功能的顺序.它重新插入所有先前删除的在当前事件点没有其端点的段(因为此时必须从结构中删除它们)并另外插入来自L的段 (从这一点开始).它检查新交叉点当前事件点上方和下方的顶部和底部邻居,如果发现任何交叉点,则将它们添加为事件点.
 这样,该算法对于所有类型的退化都是鲁棒的,包括垂直段和重叠段,以及在它们的端点上相交的段.

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