我试图在java中实现bentley-ottmann算法，但是我在实际实现swap操作（参见：wikipedia上的bentley-ottmann）时遇到了困难，这是处理交叉点时所需要的。
如果我正确理解了算法，有3种不同类型的事件点：
起点：这是线段的最左侧点，将此线段添加到树中，并检查它是否与此线段正上方和正下方的线段相交（如果存在）
端点：这是线段的最右侧点，从树中删除此线段，并检查正上方和正下方的线段是否相互相交
交点：这是两段的交点，交换两段在树中的位置[…]
（我省略了很多细节，因为它们在这里不太相关）
我用的是 TreeMap 作为我的数据结构来存储我的段。我不认为有什么问题 swap 操作 TreeMaps 这让你只需要交换两个元素，所以这就是我被卡住的地方。
1条答案
按热度按时间mum43rcc1#
当人们试图实现宾利奥特曼（bentley-ottmann）时，会出现很多这种情况。例如，请参见使用avl树实现bentley–ottmann算法。
热释光；dr：您不能使用像这样的标准自平衡二叉树实现
TreeMap宾利·奥特曼的国家结构。当大多数人使用像avl树或红黑树这样的平衡二叉树时，它与树中元素的不可变顺序相结合。3总是大于2。永远不需要交换它们。但是对于bentley-ottmann，排序是扫描点的函数，这意味着算法需要直接与树一起重新排序元素。在某些树中，可以侵入可变的比较器，但即使如此，说服树重新考虑其顺序的唯一方法是删除元素，更新比较器，然后重新插入元素——这比它应该的要慢得多。
此外，由于直接访问树中元素的频率，使用独立（突出）树结构更难实现最佳实现。当一条线段结束时，您希望在o（1）中直接到达该线段在树中的节点，而不是在o（logn）中沿着树蜿蜒到达该线段。这意味着您的段结构应该作为树节点起双重作用，而不是以某种方式导航到树节点。
好消息是：你可以实现你自己的平衡二叉树！玩得开心如果您以前没有实现过，我建议使用aa树。但是，如果你想寻找更多的挑战，并希望有一个更奇特的结构往往是一个完美的匹配宾利奥特曼的正常访问模式，尝试treap。
从另一个Angular 看，如果你想让某些东西快速工作，而不关心技术上的渐近界限，可以考虑只使用链表作为状态结构，通过线性扫描而不是树遍历来定位节点。根据我的经验，定位状态节点的时间很少是bentley-ottmann系统的瓶颈，如果你只处理成百上千个片段，那么二叉树的对数查找就没有意义了。