algorithm - 查找段的邻居(Bentley-Ottmann 算法)

Question

我正在实现 Bentley-Ottmann 算法找到一组线段交点，
不幸的是我不明白一些事情。

例如:

• 如何获取图像中片段 Sj 的邻居。

我正在为 sweepLine 状态使用平衡二叉搜索树，但在阅读此 wikipedia article 后，我们将段存储在叶子中我没有找到这个操作的解释。

来自引用书(de Berg & al.: "Computational Geometry"，第 25 页):

Suppose we search in T for the segment immediately to the left of some point p that lies on the sweep line. At each internal node v we test whether p lies left or right of the segment stored at v. Depending on the outcome we descend to the left or right subtree of v, eventually ending up in a leaf. Either this leaf, or the leaf immediately to the left of it, stores the segment we are searching for.

对于我的例子，如果我按照这个我会到达叶子 Sj 但我只会知道左边的叶子，即 Sk，我怎样才能得到 Si?

编辑我找到了这个 discussion这看起来像我的问题，不幸的是，没有关于如何在这种数据结构中实现某些操作的答案。

操作是:

• 在这样的数据结构中插入一个节点。
• 删除一个节点。
• 交换两个节点。
• 搜索邻居的节点。

当我们也在内部节点中存储数据时，我知道如何在平衡二叉搜索树中实现这些操作，但是对于这种类型的 AVL，我不知道它是否是同一回事。

谢谢

Answer 1

我在阅读 Computational Geometry from DeBerg 时偶然发现了同样的问题(请参阅第 25 页的引述和图片)。我的理解如下:

假设您需要树中段 S 的右邻居。如果您在节点中存储数据，伪代码是:

locate node S
if S has a right subtree:
   return the left-most node of the right subtree of S
else if S is in the left sub-tree of any ancestor:
   return the lowest/nearest such ancestor
else
   return not found

如果您将数据存储在叶子中，伪代码将变为:

let p the point of S currently on the sweep line
let n the segment at the root of the tree

while n != null && n is not a leaf:
   if n = S:
     n = right child of S
   else:
     determine if p is on the right or left of n
     update n accordingly (normal descent)

最后，要么n为空，意味着没有右邻居，要么n指向正确的叶子。

同样的逻辑适用于左邻居。