您可以从此页面尝试使用以下伪代码尝试Bentley–Ottmann

Bentley-Ottmann算法

Bentley-Ottmann算法的输入是线段Li的集合OMEGA = {Li}，其输出将是交点的集合LAMBDA =
{Ij}。该算法被称为“扫掠线算法”，因为它的操作可以可视化为具有另一条线，即“扫掠线”
SL，扫过集合OMEGA并在信息经过各个段Li时收集信息。从SL的每个位置收集的信息基本上是OMEGA中当前正由SL相交的所有段的有序列表。维护此信息的数据结构通常也称为“扫描线”。当发现相交时，此类结构还检测并输出相交。它发现路口的过程是算法的核心及其效率。

要实现扫描逻辑，我们必须首先对OMEGA的片段进行线性排序，以确定SL遇到它们的顺序。也就是说，我们需要对所有段Li中的端点{Ei0，Ei1} i =
1，n进行排序，以便我们可以检测到SL开始和停止与OMEGA的每个段相交的时间。传统上，通过先增加x然后增加y坐标值来对端点进行排序，但是可以采用任何线性顺序（某些作者更喜欢先减少y然后增加x）。按照传统的排序方式，扫掠线是垂直的，在遇到每个线段时从左向右移动，如下图所示：

横扫线

在算法中的任何一点上，扫掠线SL仅与那些线段相交，其端点在其左侧（或上方），而另一端点在其右侧。SL数据结构通过以下方式保留这些段的动态列表：（1）在遇到最左边的端点时添加一个段，以及（2）在遇到最右边的端点时删除一个段。此外，SL用“上下”关系对段列表进行排序。因此，要添加或删除段，必须确定其在列表中的位置，这可以通过对列表中当前段进行最坏情况的O（log-n）二进制搜索来完成。此外，除了添加或删除句段外，还有另一个事件会更改列表结构。也就是说，只要两个线段相交，就必须交换它们在有序列表中的位置。鉴于这两个部分，

为了组织所有这些，算法维护一个有序的“事件队列”
EQ，其元素导致SL段列表中的更改。最初，将EQ设置为所有段端点的扫描顺序列表。但是，当找到线段之间的交点时，它们也将以与端点相同的扫描顺序添加到EQ中，但是必须避免，以避免将重复的交点插入事件队列。上图中的示例显示了这种情况如何发生。在事件2中，线段S1和S2导致要计算交点I12并将其放置在队列中。然后，在事件3中，段S3介于S1和S2之间，并将它们分开。接下来，在事件4中，S1和S3交换在扫描线上，并且S1再次与S2相邻，从而再次计算I12。但是，每个路口只能有一个事件，和I12不能两次放入队列。因此，当将交叉路口放入队列时，我们必须在队列中找到其潜在的x排序位置，并检查其是否已经存在。由于任何两个线段最多有一个相交点，因此用这些线段的标识符标记一个相交就足以唯一地标识它。所有这些的结果是，事件队列的最大大小=
2n + k.le.2n + n2，并且任何插入或删除操作都可以用O（log（2n + n2））= O（log-n ）二进制搜索。

但是，这与有效地找到完整的路段交叉点集有什么关系？好吧，随着将片段顺序添加到SL片段列表中，就确定了它们与其他合格片段的可能交集。找到有效的相交后，会将其插入事件队列。此外，当在扫描期间处理EQ上的交集事件时，它将导致对SL列表进行重新排序，并且该交集也将添加到输出列表LAMBDA中。最后，在处理完所有事件后，LAMBDA将包含所有路口的完整有序集合。

但是，我们仍然需要描述一个关键细节，即算法的核心。即，如何计算有效的交集？显然，两个线段只有在某个时间同时出现在扫掠线上时才能相交。但这本身不足以使算法高效。重要的观察结果是，两个相交的线段必须在扫掠线上紧邻的上下相邻线。因此，只有少数几种受限制的情况需要计算可能的交点：

将段添加到SL列表后，请确定其是否与上方和下方的邻居相交。

当从SL列表中删除一个段时，该段的上一个和下一个相邻邻居将被合并为新的邻居。因此，需要确定它们可能的交点。

在相交事件中，两个段在SL列表中切换位置，并且必须确定它们与新邻居的相交（每个相交）。这意味着要处理EQ的任何一个事件（端点或交点），最多需要确定两个交点。

剩下一个细节，即从SL结构中添加，查找，交换和删除段所需的时间。为此，SL可以实现为平衡的二叉树（例如AVL，2-3或红黑树），从而保证自n以来这些操作最多需要O（log-n）时间。是SL列表的最大大小。因此，（2n
+ k）事件中的每一个都有最差的O（log-n）处理要做。将初始排序和事件处理相加，算法的效率为：O（nlog-n）+ O（（2n + k）log-n）=
O（（n + k）log-n）。

伪代码：Bentley-Ottmann算法

综上所述，Bentley-Ottmann算法实现的顶层逻辑由以下伪代码给出：

    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;
}

此例程输出所有交点的完整有序列表。