使用快速插入的矩形空间索引

Question

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

我已经研究了R-树、R+树、kD-树、四叉树和B-树，但据我所知，插入通常很慢。我希望插入时间复杂度为亚线性，所以也许有人能证明我对列出的任何数据结构都是错误的。

我应该能够查询数据结构，以了解哪些矩形在点(x,y)处或哪些矩形与矩形(x, y, 宽度, 高度)相交。

编辑: 我之所以希望插入速度快，是因为如果你想象一个矩形在屏幕上被移动，它们将不得不被删除并重新插入。

谢谢！

- TheCloudlessSky

---

也许我有所遗漏，但是如何在次线性时间内进行插入呢？仅读取每个矩形的坐标已经是O(n)操作了。 - Mark Byers

如果“屏幕”中的所有对象都已经被索引（kd、quad、r/trees），那么插入操作的时间复杂度应该小于O(n)，因为你不需要遍历每个对象... - TheCloudlessSky

如果矩形移动速度有限，那么询问是否有一种分摊重建过程的方法是合理的。 - user287792

好吧，它们并不总是在移动。假设您拿起鼠标并将一个对象拖动到屏幕上，这是“运动”发生的很好的例子。 - TheCloudlessSky

Answer 1

我会采用多尺度网格方法（在某种形式上等同于四叉树）。

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

为每个像素设置一个矩形列表数组。然后，进行二进制分类，再次进行分类。一直重复，直到有一个像素覆盖了所有内容。

现在，关键是要将矩形插入到与矩形大小相匹配的级别中。这将类似于（像素大小）〜min（height，width）/ 2。现在，对于每个矩形，您只需将其插入到列表中即可（您可以将其上限绑定为常量，例如选择具有4到16个像素之间的内容）。

如果要查找x，y处的所有矩形，则在最小像素的列表中查找，然后在包含它的2x2分组像素的列表中查找，然后在4x4等中查找；您应该有log2（# of pixels）步骤可供查看。（对于较大的像素，您需要检查（x，y）是否真的在矩形内；您预计边界上约有一半的成功率，而在矩形内则全部成功，因此您不应比直接查找像素时多出2倍以上的工作量。）

现在，插入操作怎么样？那非常便宜 - 在列表的前面插入O（1）。

删除操作怎么样？那就更昂贵了。您必须查看每个像素中重叠的矩形数量，并为每个像素输入修复每个列表。在空间中，这大约是O（n），而且大小大致相同。如果您有非常多的矩形，则应使用其他数据结构来保存它们（哈希集，RB树等）。

（请注意，如果最小矩形必须大于一个像素，则不需要实际形成多尺度结构一直到像素级别；只需下降到最小矩形不会在分组像素内迷失即可。）

- Rex Kerr

Answer 2

这可能更像是一条扩展评论而不是答案。

我有些困惑你真正想要什么。我猜测你想要一个数据结构来支持快速回答问题，例如“给定一个矩形的ID，返回其当前坐标”。对吗？

还是你想回答“位置(x,y)上的哪个矩形”？在这种情况下，具有与显示高度和宽度相匹配的维度的数组可能足够了，数组中的每个元素都是该像素上的矩形的（短）列表。

但是，你提到需要一种插入算法尽可能快地处理不断移动的矩形。如果屏幕上只有10个矩形，你可以简单地使用一个包含每个矩形坐标的10个元素数组。更新它们的位置则不需要向数据结构中插入任何内容。

有多少个矩形？它们创建和销毁的速度有多快？你想如何应对重叠？矩形只是边界，还是包括内部？

- High Performance Mark

Answer 3

你提到的数据结构是相当混合的：特别是B-Tree应该很快（插入成本随存储项数的对数增长），但不会加速你的交集查询。

忽略这些，并希望一切顺利，空间数据结构分为两部分。第一部分告诉你如何从数据构建树形结构。第二部分告诉你如何跟踪每个节点上描述其下方存储项的信息，并如何使用它来加速查询。

通常情况下，你可以采用保留每个节点信息的想法，而不使用（昂贵的）确切树状结构构建的想法。例如，你可以通过比特交织一个矩形的坐标点来创建一个密钥，然后使用完全普通的树形结构（如B-Tree、AVL Tree或红黑树）来存储它，同时仍然保持每个节点的信息。这可能在实践中足以加速查询 - 尽管你只能在实现并在实际数据上测试它之后才能知道。大多数方法中构建树形指令的目的是提供性能保证。

两个附言：

1) 对于这个问题，我喜欢使用 Patricia 树 - 它们相对容易实现，并且添加或删除条目不会太大程度地破坏树结构，因此您不需要太多工作来更新存储在节点中的信息。

2) 上次我看过一个窗口系统时，它根本不关心任何这些聪明的东西 - 它只是保持一个线性列表，并在需要时全部搜索：那已经足够快了。

- mcdowella