了解宾利奥特曼算法

Question

这是代码：

Initialize event queue EQ = all segment endpoints; 
    Sort EQ by increasing x and y; 
    Initialize sweep line SL to be empty; 
    Initialize output intersection list IL to be empty; 

    While (EQ is nonempty) { 
     Let E = the next event from EQ; 
     If (E is a left endpoint) { 
      Let segE = E's segment; 
      Add segE to SL; 
      Let segA = the segment Above segE in SL; 
      Let segB = the segment Below segE in SL; 
      If (I = Intersect(segE with segA) exists) 
       Insert I into EQ; 
      If (I = Intersect(segE with segB) exists) 
       Insert I into EQ; 
     } 
     Else If (E is a right endpoint) { 
      Let segE = E's segment; 
      Let segA = the segment Above segE in SL; 
      Let segB = the segment Below segE in SL; 
      Delete segE from SL; 
      If (I = Intersect(segA with segB) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
     } 
     Else { // E is an intersection event 
      Add E’s intersect point to the output list IL; 
      Let segE1 above segE2 be E's intersecting segments in SL; 
      Swap their positions so that segE2 is now above segE1; 
      Let segA = the segment above segE2 in SL; 
      Let segB = the segment below segE1 in SL; 
      If (I = Intersect(segE2 with segA) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
      If (I = Intersect(segE1 with segB) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
     } 
     remove E from EQ; 
    } 
    return IL; 
} 

我在左端点的情况下 如果a或b犯规存在哪些例如几个问题吗？如果存在并且不是，我们是否应该检查第二个，如果没有或没有？

在第一次迭代中，SL大部分是空的，因此在开始时大部分点被删除而未被使用。那是什么意思？

Answer 1

如果a和b不存在，那么当然与它们没有交集是可能的。如果只有一个存在，那么只有那个可以检查相交。

我不确定你的意思是关于“未经使用而被移除”的点。事件队列中的所有事件都很重要，要么是因为它们即将到来的交叉路口，要么是通过保持扫描线保持最新状态来设置潜在即将到来的交叉路口。

最后是Bentley-Ottmann，而不是Bentley-Ottoman。