相关疑难解决方法(0)

Bentley-Ottoman算法查找一组线段中的所有交叉点.对于一个众所周知且重要的算法,Bentley-Ottmann算法的C++实现似乎很奇怪 - 可以处理所有退化情况的实现(即,对扫描线和交叉点的数量没有特殊假设,等等on) - 根本没有.我能找到的唯一代码就在这里,但它似乎没有处理广义的情况.

Bentley-Ottmann算法是否已经在任何经过​​良好测试的库中实现,例如Boost或LEDA？如果是的话,我可以参考吗？

我在 C# 中正确实现 Bentley-Ottmann 算法时遇到了一些麻烦。我试图根据这里的伪代码来实现它。我在下面发布了我的主要代码。假设 myBST和PriorityQueueclasses 实现正确，您是否发现代码有任何问题？

没有错误，但不是所有的交点都找到了，只有一些。我的猜测是else代码部分有错误（当前事件是交点时）。通过交换 BST 中两个段的位置，我不确定伪代码是什么意思。我这样做的方式好吗？因为最终，两者在 BST 中并没有真正交换。我也不能只是改变他们的位置，因为这可能会破坏 BST 属性。

另外，我是否正确假设段在 BSTY中按其左端点的坐标排序？

我注意到的另一个我似乎无法追踪的错误是，有时要点(0, 0)进入eventList. 在没有交集的情况下(0, 0)输出Geometry.Intersects，但在这种情况下，if条件应该阻止它被添加。我不知道它是如何进入的。如果我eventList在添加一个点后打印 的内容，则(0, 0)永远不会出现。如果我在提取和弹出元素后打印内容，(0, 0)有时会出现。这可能与Pop()混淆引用的方法有什么关系，还是我的PriorityQueue实现中绝对有问题？

如果需要，我也可以展示我对 BST 和优先级队列的实现。

static class BentleyOttman
{
    private static void AddIntersectionEvent(PriorityQueue eventList, Segment segEv, Segment segA, SegPoint i)
    {
        i.IntersectingSegments = new Tuple<Segment, Segment>(segEv, segA);
        i.Type = …