You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

关于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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.06.30 15:13:14