Bentley-Ottmann 算法：Java 中的交换操作
Bentley-Ottmann algorithm: swap operation in Java
我正在尝试在 Java 中实现 Bentley-Ottmann 算法，但我在实际实现处理交点时所需的交换操作（参见：Bentley-Ottmann on Wikipedia）时遇到了困难。
如果我对算法的理解正确，有 3 种不同类型的事件点：
- 起始点：这是线段的最左边的点，将此线段添加到树中并检查它是否与线段正上方和下方的线段相交（如果他们存在）
- 端点：这是线段的最右边的点，从树中移除这条线段并检查正上方和下方的线段是否彼此相交
- Intersection-point：这是两个线段的交点，交换两个线段在树中的位置[...]
（我省略了很多细节，因为它们在这里不是很相关）
我使用 TreeMap 作为我的数据结构来存储我的段。我不认为 TreeMaps 有一个 swap 操作可以让你只交换两个元素，所以这就是我卡住的地方。
人们在尝试实施 Bentley-Ottmann 时经常会遇到这种情况。例如，参见 Implementing Bentley–Ottmann Algorithm with an AVL tree .
tl;dr：您不能对 Bentley-Ottmann 中的状态结构使用标准的自平衡二叉树实现，例如 TreeMap。
当大多数人使用像 AVL 树或红黑树这样的平衡二叉树时，它与树中元素的不可变排序相结合。 3 总是大于 2。永远不需要交换它们。但对于 Bentley-Ottmann，排序是扫描点的函数，这意味着算法需要直接参与树对元素的重新排序。在某些树中，可以修改可变比较器，但即便如此，说服树重新考虑其顺序的唯一方法是删除元素，更新比较器，然后重新插入元素——这要慢得多比它应该的。
此外，由于您直接访问树中元素的频率，使用独立（扩展）树结构使得实现最佳实现变得更加困难。当一条线段结束时，您想 直接 到 O(1) 树中该线段的节点，而不是在 O(log n) 中沿着树蜿蜒到它。这意味着您的 Segment 结构应该充当树节点的双重职责，而不是通过某种方式导航到树节点。
好消息是：您可以实现自己的平衡二叉树了！玩得开心。 ;-) 如果您之前没有实施过，我建议您使用 AA tree. But if you're looking for more of a challenge, and would like a more exotic structure which tends to be a perfect match for Bentley-Ottmann's normal access patterns, try a Treap.
从另一个方向看，如果你想让某些东西快速工作并且你不关心技术渐近边界，请考虑只使用链表作为你的状态结构，通过线性扫描而不是通过线性扫描定位节点树遍历。根据我的经验，定位状态节点的时间很少是涉及 Bentley-Ottmann 的系统的瓶颈，如果您只处理数百或数千个段，则二叉树的对数查找将不重要。
我正在尝试在 Java 中实现 Bentley-Ottmann 算法，但我在实际实现处理交点时所需的交换操作（参见：Bentley-Ottmann on Wikipedia）时遇到了困难。
如果我对算法的理解正确，有 3 种不同类型的事件点：
- 起始点：这是线段的最左边的点，将此线段添加到树中并检查它是否与线段正上方和下方的线段相交（如果他们存在）
- 端点：这是线段的最右边的点，从树中移除这条线段并检查正上方和下方的线段是否彼此相交
- Intersection-point：这是两个线段的交点，交换两个线段在树中的位置[...]
（我省略了很多细节，因为它们在这里不是很相关）
我使用 TreeMap 作为我的数据结构来存储我的段。我不认为 TreeMaps 有一个 swap 操作可以让你只交换两个元素，所以这就是我卡住的地方。
人们在尝试实施 Bentley-Ottmann 时经常会遇到这种情况。例如，参见 Implementing Bentley–Ottmann Algorithm with an AVL tree .
tl;dr：您不能对 Bentley-Ottmann 中的状态结构使用标准的自平衡二叉树实现，例如 TreeMap。
当大多数人使用像 AVL 树或红黑树这样的平衡二叉树时，它与树中元素的不可变排序相结合。 3 总是大于 2。永远不需要交换它们。但对于 Bentley-Ottmann，排序是扫描点的函数，这意味着算法需要直接参与树对元素的重新排序。在某些树中，可以修改可变比较器，但即便如此，说服树重新考虑其顺序的唯一方法是删除元素，更新比较器，然后重新插入元素——这要慢得多比它应该的。
此外，由于您直接访问树中元素的频率，使用独立（扩展）树结构使得实现最佳实现变得更加困难。当一条线段结束时，您想 直接 到 O(1) 树中该线段的节点，而不是在 O(log n) 中沿着树蜿蜒到它。这意味着您的 Segment 结构应该充当树节点的双重职责，而不是通过某种方式导航到树节点。
好消息是：您可以实现自己的平衡二叉树了！玩得开心。 ;-) 如果您之前没有实施过，我建议您使用 AA tree. But if you're looking for more of a challenge, and would like a more exotic structure which tends to be a perfect match for Bentley-Ottmann's normal access patterns, try a Treap.
从另一个方向看，如果你想让某些东西快速工作并且你不关心技术渐近边界，请考虑只使用链表作为你的状态结构，通过线性扫描而不是通过线性扫描定位节点树遍历。根据我的经验，定位状态节点的时间很少是涉及 Bentley-Ottmann 的系统的瓶颈，如果您只处理数百或数千个段，则二叉树的对数查找将不重要。