Bentley-Ottmann算法扫描线段顺序判定疑问：交点M、N漏检咨询

你的错误出在新线段插入时的相邻线段交点处理环节，核心是两个关键步骤被遗漏：

1. 未移除被新线段隔开的原相邻线段对的交点事件 #

当扫描线触及E并将EF插入状态后，原本相邻的C和A被EF隔开，不再是扫描线状态中的相邻线段。此时必须从事件队列中删除之前检测到的C与A的交点L——因为算法中只有相邻线段的交点才需要加入事件队列，非相邻线段的交点会在后续它们重新成为相邻线段时再检测。如果保留L事件，后续处理时错误交换C和A的顺序，会导致EF始终处于两者之间，后续EF被移出后也无法触发M、N的检测。

2. 插入新线段时未与左右邻居分别检测交点 #

插入EF时，不能仅确定它在C和A之间就停止操作，必须执行两个检测：

• 检测EF与左侧线段C的交点M，若M位于当前扫描线下方（属于未来要处理的事件），则将M加入事件队列；
• 检测EF与右侧线段A的交点N，若N位于当前扫描线下方，则将N加入事件队列。

你跳过了这两次检测，导致M、N从未进入事件队列，后续EF被移出状态后，C和A重新相邻时，扫描线已经错过M、N的位置，自然无法检测到这两个交点。

关键逻辑补充 #

Bentley-Ottmann算法的扫描线状态维护规则：

• 插入线段：找到插入位置后，先移除原左、右邻居之间的交点事件（如果存在），再分别与左、右邻居检测交点，将有效交点加入事件队列；
• 删除线段：移除线段后，检测原左、右邻居之间的交点，若有效则加入事件队列。

按照这个逻辑修正后，插入EF时就能正确捕获M、N，后续处理时不会出现漏检。

内容的提问来源于stack exchange，提问作者SynchronizX