c# - 使用 2 维时，R 树能否保持 z 顺序？

Question

我正在基于 Guttman 的原始论文编写 R-Tree 的实现。我正在考虑将 R-Tree 用于我正在编写的程序，该程序涉及屏幕上的许多矩形，可以用鼠标移动/重新调整大小。

我只想有效地选择特定矩形中的矩形并绘制它们(而不是遍历可能超过 100 个项目并检查边界是否相交)。在阅读了几篇 Guttman 的论文后，我发现的问题是无法为 2D 对象维护 z 顺序。

例如，如果我移动一个对象，它会被删除然后重新插入。重新插入时，插入的节点将无法跟踪正确的顺序。我见过的大多数 R-Tree 实现都使用数组并找到空位置。重新插入基本上会破坏任何 z 顺序定位。

所以当我去绘制所有与矩形相交的矩形时，它们返回的顺序不一定正确。

我这个假设错了吗？我在考虑不使用数组，而是可以使用 AVL 或红黑树并使用 Comparer 比较 z-index 以插入到树中。这样，始终保持 z 顺序(这是最重要的因素)。

我也只是想在它们退回时对它们进行分类，但我认为这可能会更昂贵。

Answer 1

R-tree 不应该以某种方式对答案记录进行排序。

只需对答案进行排序。还不算太慢。

顺便说一句，我可以把我的 r-tree 代码邮寄给你。它对我来说很好用，但如果有人检查一下 Guttman 或 Beckman 在他们的论文中写的是什么，那将非常有用......

空间索引的顺序与严格顺序有本质的不同……这是空间索引和 B+ 树之间的区别。

你也可以有两个索引并连接它们。您真的确定需要索引吗？运行缓慢？