我已经实现了 Bentley-Ottmann 算法，还处理了这里提到的边缘情况：http ://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm#Special_position_and_numerical_precision_issues 。
但是，它仍然不适用于所有线段，例如这个，仅找到左侧交点，但没有找到第二个（当提取第一个交点时，左侧的前 2 行在扫描线字典中反转作为来自事件优先级队列的事件）：
或者在有点复杂的情况下，仍然只能识别左侧的第一个交叉点：
我应该在算法中添加什么或更改它以考虑这种情况（当然要保持其 O(n log n) 复杂度）？
编辑：另一个“肮脏”的例子，这次没有找到交叉点：
编辑 2：从第 28 页开始，请参见此处的算法伪代码和模拟： http ://www-ma2.upc.es/vera/wp-content/uploads/2012/10/intersection-of-segments.pdf