矩形边界内的有效点搜索

Question

我正在使用矢量地图编辑器,我有一组元素,每个元素都在视图中指定其边界框.当鼠标移动时,我想突出显示第一个元素,其边界框包含当前鼠标位置.现在我使用一个简单的列表并通过它,但由于元素的数量可能会增加,当前搜索算法的O(n)复杂性对于交互式应用程序将是有问题的.

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

一些额外的约束/要求:

• 将填充边界框的数据结构必须是相对快速的(因为我需要做的,每次地图移动或变焦或投影的变化).
• 该算法必须能够找到所有匹配元素(而不仅仅是第一个).原因是一些地图元素可能具有不规则的形状,因此简单的边界框匹配不够严格.然后我会查看匹配列表并进行精确匹配.
• 的顺序,其中所述盒被添加到所述一组需要保持某种方式-其被上述另一元件得出匹配他们的边界框时,应具有优先级的映射元素.

Answer 1

通过书籍浏览后，我发现一个答案计算几何（3第237页。该书^RD版，2008）。这种类型的搜索通常称为“ 刺刺查询”，通常使用段树来实现。

复杂性：

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