Bentley-Ottmann 算法：Java 中的交换操作

Question

我正在尝试在 Java 中实现 Bentley-Ottmann 算法，但一直停留在实际实现处理交点时所需的交换操作（参见：维基百科上的 Bentley-Ottmann ）。

如果我正确理解该算法，则有 3 种不同类型的事件点：

1. 起点：这是线段的最左边的点，将此线段添加到树中并检查它是否与该线段正上方和下方的线段相交（如果存在）
2. 终点：这是线段的最右边的点，从树中删除该线段并检查正上方和下方的线段是否彼此相交
3. 交点：这是两个线段的交点，交换两个线段在树中的位置[...]

（我省略了很多细节，因为它们与这里不太相关）

我使用 aTreeMap作为我的数据结构来存储我的段。我不认为有一个swap操作TreeMaps可以让你只交换两个元素，所以这就是我陷入困境的地方。

Answer 1

当人们尝试实施 Bentley-Ottmann 时，这种情况经常出现。例如，请参阅使用 AVL 树实现 Bentley\xe2\x80\x93Ottmann 算法。

\n

tl;dr：您不能使用标准的自平衡二叉树实现，例如TreeMapBentley-Ottmann 中的状态结构。

\n

当大多数人使用平衡二叉树（如 AVL 树或红黑树）时，它与树中元素的不可变排序相结合。3 总是大于 2。永远不需要交换它们。但对于 Bentley-Ottmann，排序是扫描点的函数，这意味着算法需要直接参与树对元素的重新排序。在某些树中，可以侵入可变比较器，但即使如此，说服树重新考虑其顺序的唯一方法是删除元素，更新比较器，然后重新插入元素——这非常困难。 ，比应有的速度慢得多。

\n

此外，由于直接访问树中元素的频率，使用独立（突出）的树结构使得实现最佳实现变得更加困难。当线段结束时，您希望在 O(1) 内直接到达树中该线段的节点，而不是在 O(log n) 内沿着树蜿蜒到达该节点。这意味着您的 Segment 结构应该充当树节点的双重职责，而不是通过某种方式导航到树节点。

\n

所以好消息是：您可以实现自己的平衡二叉树！玩得开心。;-) 如果您之前没有实现过，我建议使用AA 树。但是，如果您正在寻找更多挑战，并且想要一种更奇特的结构，该结构往往与 Bentley-Ottmann 的正常访问模式完美匹配，请尝试Treap。

\n

从另一个方向看，如果您想让某些东西快速工作并且不关心技术渐近边界，请考虑仅使用链表作为状态结构，通过线性扫描而不是树遍历来定位节点。根据我的经验，定位状态节点的时间很少成为涉及 Bentley-Ottmann 的系统的瓶颈，并且如果您仅处理数百或数千个段，则二叉树的对数查找并不重要。

\n