寻找分段的邻域(Bentley-奥特曼算法)

Question

我正在实现Bentley-奥特曼算法来找到分段交点集，

不幸的是我不明白一些事情。

​

​

例如：

• 如何才能在图像中得到片段Sj的邻居。

对于sweepLine状态，我使用了一个平衡的二进制搜索树，但是我们将这些段存储在叶子中，在阅读了这个维基百科文章之后，我没有找到对这个操作的解释。

来自参考书(de Berg & al.：“计算几何”，ill )。在第25页)：

假设我们在T中搜索位于扫描线上的某个点p的左边的段。在每个内部节点v上，我们测试p是否位于存储在v上的段的左或右，取决于我们下降到v的左或右子树的结果，最终在叶子中结束。不管是这片叶子，还是它左边的那片叶子，都存储着我们正在寻找的片段。

对于我的例子，如果我遵循这个，我会到达叶子Sj，但我只知道左边的叶子，也就是Sk，我怎么能得到Si？

编辑我发现了这个看起来像我的问题的讨论，不幸的是，对于如何在这样的数据结构中实现一些操作没有答案。

该行动是：

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

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

谢谢

Answer 1

我在阅读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为null，这意味着没有右邻居，要么n指向正确的叶子。

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

Answer 2

和你一样，我在阅读“计算几何”时也遇到了同样的问题。但我认为，C++标准模板库(STL)有一个名为“地图”的植入，可以完成这项工作。

您只需要为线段和事件点及其比较函数定义一些个性化的类。然后，使用std::map构建树并使用map.find()访问相邻元素以获取和迭代，并使用迭代器获得对两个相邻元素的访问权限。