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

Question

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

javaalgorithmgeometrycomputational-geometry

3

我正在尝试在Java中实现Bentley-Ottmann算法，但是在处理交点时需要实现交换操作（参见：Wikipedia上的Bentley-Ottmann），我卡住了。

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

起点：这是线段的最左端点，将此线段添加到树中，并检查它是否与直接位于该线段上方和下方的线段（如果存在）相交。
终点：这是线段的最右端点，从树中删除此线段并检查直接位于其上方和下方的线段是否相互相交。
交点：这是两条线段的交点，请在树中交换两条线段的位置[...]

（由于这里不是很相关，所以我略去了许多细节）

我正在使用 TreeMap 作为存储片段的数据结构。我认为在 TreeMaps 中没有 swap 操作让你只需交换两个元素，这就是我卡住的地方。

- mrMoonpenguin

TreeMap是有序的，因此交换元素没有意义，因为元素的顺序始终是排序的。 - MrSmith42

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sneftel · Accepted Answer

这个问题在人们尝试实现 Bentley-Ottmann 算法时经常出现。例如，参见使用 AVL 树实现 Bentley-Ottmann 算法。

简而言之，你不能使用标准的自平衡二叉树实现，比如 TreeMap，作为 Bentley-Ottmann 状态结构。

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

此外，使用独立的（外部的）树结构会使实现最优解更加困难，因为您会频繁地直接访问树中的元素。当一条线段结束时，您希望直接以 O(1) 的时间到达树中该线段的节点，而不是沿树向它走去，需要 O(log n) 的时间。这意味着您的线段结构应该具有双重职责，即作为树节点，而不是通过某种方式导航到树节点。

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

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