查找与给定点相交的所有边界框(使用树结构)

Question

我创建了一个函数，该函数循环遍历 2d 边界框列表并找到包含给定 2d 点的边界框。不幸的是，这很慢，所以我正在寻找一种使用某种树结构来优化它的方法。

我见过很多基于在框中查找点的问题，但没有一个基于从点查找框的问题。我知道如何进行交叉，所以这只是我感兴趣的树结构。我认为四叉树可能适合，但我不确定它如何处理在不同节点中复制的边界框。

最好使用某种二叉搜索树，递归地拆分 x 轴和 y 轴（如中位数切割）？

Answer 1

我建议您使用段树。

请看这些幻灯片：

http://algo.kaust.edu.sa/Documents/cs372l07.pdf

您特别在寻找一种在更高维度上刺伤查询的解决方案（幻灯片 25）