高效地在矩形边界内查找点

Question

我正在开发一个矢量地图编辑器，有一组元素，每个元素都在视图中指定了其边界框。随着鼠标移动，我想要高亮显示第一个包含当前鼠标位置的边界框的元素。目前我使用一个简单的列表并进行遍历，但随着元素数量的增加，当前搜索算法的O(n)复杂度将成为交互式应用程序的问题。 那么，有什么更好的算法/数据结构可以解决这个问题呢？ 一些额外的约束/要求：

• 填充边界框数据结构必须相对快速（因为我需要每次地图移动或缩放或投影变化时都执行该操作）。
• 算法必须能够找到所有匹配的元素（而不仅仅是第一个）。原因是某些地图元素可能具有不规则的形状，因此简单的边界框匹配不够严格。然后我会浏览匹配列表并进行精确匹配。
• 添加到集合中的框的顺序需要以某种方式得以维护 - 在另一个元素上方绘制的地图元素在匹配其边界框时应具有优先级。

- Igor Brejc

---

有内存限制吗？如果没有：您可能想使用查找表。 - amit

我故意没有提到内存限制，因为我想听取几个想法，然后在速度/内存权衡方面做出判断。您能否在这种情况下更具体地谈谈查找表？ - Igor Brejc

Answer 1

在查阅了多本书后，我在计算几何一书中找到了一个答案（第三版，第237页；2008年）。这种类型的搜索通常被称为射线查询，通常使用线段树来实现。

复杂度：

• 查询：O(log2n + k)，其中k是报告的边界框数目
• 数据结构使用O(n*log n)存储空间
• 该结构可以在O(n*log n)时间内构建

- Igor Brejc

Answer 2

如果您按较低的x位置对元素进行排序，则可以跳过某个点之前的所有元素。 如果您有第二个具有上部x位置的列表，则知道何时完成。

另一个想法：创建一个网格，将整个区域分割成100x100的部分。 现在一次找出，在您的网格中哪些部分有图形重叠：

5
4
3    xx 
2  xxxx
1  xx
0
 0 1 2 3 4 5 

对于这个图形，它将是(1,1),(1,2)(2,2)(2,3) 一个x*y的列表地图现在将包含这个形状s，对应着4个位置(1,1)->s，(1,2)->s，...

如果你很少插入/删除，但经常比较，这将加快你的搜索速度。你只需要访问与特定单元格相关联的形状，并调查这些形状的确切坐标。

- user unknown

---

有关 x*y 列表的有趣想法。这肯定会加快速度（取决于网格的细度），尽管我猜 O(n) 的复杂度仍然存在。 - Igor Brejc

Answer 3

查找表：用户倾向于返回屏幕上相同的区域（因此边缘访问率通常很低，中心访问率通常很高）。因此，我们可以利用这些知识来提高性能。
在找到一个点后（可以是任何其他查找方法），您可以将结果缓存为列表，下次用户访问相同的位置时，查找将是O（1）。当然，您需要在添加新形状后清除缓存。

另一种可能性是使用观察者模式，每个新形状都会在所需的点注册自己（这可能很昂贵，具体取决于插入形状的频率...），一旦鼠标在该点上，它只需调用注册到该点的人员即可。

第三种可能性当然是缩小搜索区域，就像@user unknown建议的那样。这种可能性可以与查找表结合使用。

- amit

---

“访问相同的位置”是指相同的X，Y坐标吗？考虑到现今屏幕分辨率和鼠标灵敏度的增加，用户能否捕捉到相同的坐标？虽然我得承认这是一个有趣的想法 - 但可能需要结合其他方法，正如你所建议的那样。 - Igor Brejc

@Igor：如果你担心这个问题，你可以像@user unknown建议的那样将其分成帧。如果你这样做，这种解决方案与他的唯一区别在于如何更新查找表。我建议你也仔细研究观察者模式，这将通过使用已知的解决方案简化编码。 - amit

@Igor：注意鼠标移动是连续的，鼠标沿直线移动，而不是随机地从一个点到另一个点，这显著增加了选择同一点的机会。 - amit

问题在于地图视图不是固定的，用户可以缩放、平移和旋转地图（通常会这样做，因为这是应用程序的特性）。因此，任何缓存的查找值都会很快失效，然后才能被使用。 - Igor Brejc