algorithm - 带快速插入的矩形的空间索引

Question

我正在寻找一种为矩形提供索引的数据结构。我需要尽可能快的插入算法，因为矩形将在屏幕上移动(考虑用鼠标将矩形拖动到新位置)。

我研究过 R-Trees、R+Trees、kD-Trees、Quad-Trees 和 B-Trees，但根据我的理解，插入通常很慢。我更喜欢以亚线性时间复杂度进行插入，这样也许有人可以证明我对所列数据结构中的任何一种都是错误的。

我应该能够查询数据结构以了解哪些矩形位于点 (x, y) 或哪些矩形与矩形相交 (x, y, width, height)。

编辑:我想要插入得如此之快的原因是，如果你想到一个矩形在屏幕上移动，它们将不得不被删除然后重新插入。

谢谢!

Answer 1

我会使用多尺度网格方法(相当于某种形式的四叉树)。

我假设您使用的是整数坐标(即像素)并且有足够的空间来容纳所有像素。

有一组矩形列表，每个像素一个。然后，两个两个地装箱，然后再做一次。一次又一次，一次又一次，直到你有一个像素覆盖所有内容。

现在，关键是您插入的矩形在与矩形大小相匹配的水平。这将类似于(像素大小)~= min(高度，宽度)/2。现在，对于每个矩形，您只需向列表中插入少量内容(您可以将其绑定(bind)在一个常量之上，例如，选择 4 到 16 像素之间的内容)。

如果您想查找 x,y 处的所有矩形，您可以在最小像素列表中查找，然后在包含它的 2x2 分箱像素列表中查找，然后在 4x4 像素列表中查找，等等；您应该有 log2(# of pixels) 个步骤来查看。 (对于较大的像素，您必须检查 (x,y) 是否真的在矩形内；您希望其中大约一半在边界上成功，并且所有这些都在矩形内成功，所以您期望不比直接查找像素多 2 倍的工作量。)

现在，插入呢？这非常便宜——O(1) 使您自己排在列表的前面。

删除呢？那更贵；您必须查看并修复您输入的每个像素的每个列表。这大约是 O(n) 在空间中该位置重叠的大小大致相同的矩形 和 。如果您有大量的矩形，那么您应该使用其他一些数据结构来保存它们(哈希集、RB 树等)。

(请注意，如果您的最小矩形必须大于一个像素，则您不需要实际形成一直到像素级的多尺度结构；只需向下直到最小矩形不会无可救药地丢失在里面你的合并像素。)