algorithm - 矩形边界内的高效点搜索

Question

我正在开发一个矢量 map 编辑器，我有一组元素，每个元素都在 View 中指定了它的边界框。当鼠标移动时，我想突出显示其边界框包含当前鼠标位置的第一个元素。现在我使用一个简单的列表并遍历它，但是随着元素的数量可能会增加，当前搜索算法的 O(n) 复杂度对于交互式应用程序来说将是一个问题。

什么是更好的算法/数据结构？

一些额外的约束/要求:

• 边界框数据结构的填充必须相对较快(因为每次 map 移动或缩放或投影发生变化时我都需要这样做)。
• 算法必须能够找到所有 匹配元素(而不仅仅是第一个)。原因是有些 map 元素可以有不规则的形状，所以简单的边界框匹配不够严格。然后我会浏览匹配列表并进行一些精确匹配。
• 将框添加到集合中的顺序需要以某种方式保持 - 绘制在另一个元素之上的 map 元素在匹配它们时应该具有优先级边界框。

Answer 1

翻阅书籍后，我在Computational Geometry 中找到了一个答案。书(第 3^rd 版第 237 页；2008 年)。这种类型的搜索通常称为刺探查询，通常使用 segment trees 实现。 。

复杂性:

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