关于Bentley-Ottmann算法无法检测BC线段交点的问题咨询
Bentley-Ottmann算法交点检测问题疑惑
我正在实现Bentley-Ottmann算法,但碰到一个场景,搞不懂算法该怎么检测到某个特定交点。我画了问题的示意图:黑色线条是线段,绿色线条是扫描线(sweep line),红色线条是活跃线段排序用的y坐标,图里展示了扫描线过程的5个步骤。但照着维基百科上的算法步骤走,就是找不到BC线段的交点。
维基百科上的Bentley-Ottmann算法描述(示意图略)
具体来说:
- 在步骤3处理LeftEndpoint(C)事件时,C的y坐标比A(left)的y坐标低。按照算法要求,处理左端点事件时需要找到上方和下方的线段,先检查这两条线段是否相交并移除对应的交点事件,接着再检查新加入的线段是否和上下线段相交。这里A是C的上方线段,检查后发现A和C不相交,所以没创建任何交点事件。
- 下一步处理RightEndpoint(C)事件时,根据算法只需要检查上下线段是否相交,这里的上下线段是B和A,二者不相交,所以也没报告交点。
到这里线段C已经被完全移除了,但BC的交点始终没被报告,这明显是不对的。
请问我哪里出错了?
内容的提问来源于stack exchange,提问作者Pavlin
相关产品推荐
相关产品推荐

