使用 2 维时，R 树可以保持 z 顺序吗？
我正在根据 Guttman 的原始论文编写 R 树的实现。我正在考虑在我正在编写的程序中使用 R 树，该程序涉及屏幕上的许多矩形，可以使用鼠标移动/调整大小。
我想高效地仅选择特定矩形中的矩形并绘制它们（而不是迭代可能超过 100 个项目并检查边界是否相交）。读了几遍 Guttman 的论文后我发现的问题是二维对象的 z 顺序无法维护。
例如，如果我移动一个对象，它将被删除然后重新插入。当它重新插入时，它插入的节点将无法跟踪正确的顺序。我见过的大多数 R 树实现都使用数组，并且只找到空位置。重新插入基本上会破坏任何 z 顺序定位。
因此，当我去绘制与矩形相交的所有矩形时，它们返回的顺序不一定正确。
我的这个假设错了吗？我在想，我可以使用 AVL 或红黑树，并使用比较 z-index 的比较器来插入树中，而不是使用数组。这样，z 顺序始终得以维持（这是最重要的因素）。
我也只是想在退货时对它们进行分类，但我想这可能会更贵。
I'm writing an implementation of an R-Tree based on Guttman's original paper. I was thinking about using an R-Tree for a program I'm writing that involves a lot of rectangles on the screen that can be moved/re-sized with the mouse.
I want to efficiently only select rectangles that are in a particular rectangle and draw them (instead of iterating through potentially 100+ items and checking if bounds intersect). The problem that I'm finding after a couple reads of Guttman's paper is that z-order can't be maintained for 2D objects.
For example, if I move an object, it'd be deleted and then re-inserted. When it's re-inserted, the node it's inserted to wouldn't be able to keep track of the proper order. Most implementation's of an R-Tree that I've seen use an array and just find the empty position. The re-insertion would essentially destroy any z-order positioning.
So when I go to draw all rectangles that intersect with a rectangle, the order they're returned isn't necessarily correct.
Am I wrong on this assumption? I was thinking instead of using an array, I could use an AVL or Red-Black tree and use a Comparer that compares on z-index to insert into the tree. This way, z-order is always maintained (and it's the most important factor).
I was also just thinking of sorting them when they're returned, but this could be more expensive I'm thinking.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
R 树不应该以某种方式对答案记录进行排序。
只是排序答案。还不算太慢。
顺便说一句，我可以将我的 r-tree 代码邮寄给您。它对我来说工作得很好，但是如果有人检查它是否是 Guttman 或 Beckman 在他们的论文中写的，那将会非常有用......
空间索引的顺序与严格的顺序本质上不同......这是空间索引和 B+ 之间的区别-树。
您还可以有两个索引并将它们连接起来。
您真的确定需要索引吗？有什么东西运行缓慢？
R-tree is not supposed to order answer records somehow.
Just sort answer. It's not too slow.
BTW, I can mail you my r-tree code. It works fine for me, but it would be very useful if someone would check is it what Guttman or Beckman wrote in theirs papers...
Order of spatial indexing is essentially different from strict order...it's difference between spatial indexing and just B+-tree.
You can also have two indexes and join them.
Are you really shure you need index? Something works slow?