具有快速插入的矩形的空间索引 [英] Spatial Index for Rectangles With Fast Insert

问题描述

我正在寻找一个提供矩形索引的数据结构。我需要插入算法尽可能快，因为矩形将围绕屏幕移动（想想用鼠标拖动一个矩形到一个新的位置）。

I'm looking for a data structure that provides indexing for Rectangles. I need the insert algorithm to be as fast as possible since the rectangles will be moving around the screen (think of dragging a rectangle with your mouse to a new position).

我已经研究了R-Trees，R + Tree，kD-Trees，Quad-Trees和B-Trees，但是从我的理解插入中通常很慢。我更喜欢在亚线性时间复杂性中插入插页，所以也许有人可以证明我对任何列出的数据结构都是错误的。

I've looked into R-Trees, R+Trees, kD-Trees, Quad-Trees and B-Trees but from my understanding insert's are usually slow. I'd prefer to have inserts at sub-linear time complexity so maybe someone can prove me wrong about either of the listed data structures.

我应该可以查询数据结构为什么矩形在点（x，y）或矩形相交矩形（x，y，width，height）。

I should be able to query the data structure for what rectangles are at point(x, y) or what rectangles intersect rectangle(x, y, width, height).

编辑：我想要插入的原因这么快就是因为如果你想一个在屏幕上移动的矩形，那么它们将被删除，然后重新插入。

The reason I want insert so fast is because if you think of a rectangle being moved around the screen, they're going to have to be removed and then re-inserted.

谢谢！ p>

Thanks!

推荐答案

您提到的数据结构是一个混合的包：特别是B-Tree应该是快速的（插入成本与对数成长存在的项目数量），但不会加快您的交集查询。

The data structures you mention are quite a mixed bag: in particular B-Trees should be fast (cost to insert grows with the logarithm of the number of items present) but won't speed up your intersection queries.

忽略这一点 - 希望能够获得最佳效果 - 空间数据结构分为两部分。第一部分告诉你如何从数据中构建树结构。第二部分告诉你如何跟踪每个节点上描述存储在节点下方的信息的信息，以及如何使用它来加速查询。

Ignoring that - and hoping for the best - the spatial data structures come in two parts. The first part tells you how to build a tree structure from the data. The second part tells you how to keep track of information at each node that describes the items stored below that node, and how to use it to speed up queries.

你可以通常会捏捏关于在每个节点跟踪信息的想法，而不使用关于如何构建树的准确的（昂贵的）想法。例如，您可以通过对其点的坐标进行位交织来创建每个矩形的关键字，然后使用完全普通的树结构（如B树或AVL树或Red-Black树）来存储它仍然保持每个节点的信息。在实践中，这样做可能会加快您的查询速度 - 尽管在实际执行实际数据之前，您将无法告诉您。大多数计划中的树木建造指示的目的是提供性能保证。

You can usually pinch the ideas about keeping track of information at each node without using the (expensive) ideas about exactly how the tree should be built. For instance, you could create a key for each rectangle by bit-interleaving the co-ordinates of its points and then use a perfectly ordinary tree structure (such as a B-tree or an AVL tree or a Red-Black tree) to store it, while still keeping information at each node. This might, in practice, speed up your queries enough - although you wouldn't be able to tell that until you implemented and tested it on real data. The purpose of the tree-building instructions in most schemes is to provide performance guarantees.

两个后记：

1）我喜欢Patricia树 - 它们相当容易实现，并且添加或删除条目不会对树结构造成太大影响，所以您不需要太多的工作来更新存储在节点上的信息。

1) I like Patricia trees for this - they are reasonably easy to implement, and adding or deleting entries does not disturb the tree structure much, so you won't have too much work to do updating information stored at nodes.

2）上次我看着一个窗口系统，它并没有打扰任何这个聪明的东西 - 它只是保持一个线性列表的项目，一直搜索当它需要：这是足够快。

2) Last time I looked at a window system, it didn't bother about any of this clever stuff at all - it just kept a linear list of items and searched all the way through it when it needed to: that was fast enough.

这篇关于具有快速插入的矩形的空间索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！