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

Question

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

我已经看到很多基于查找盒子内点的问题，但没有找到从某个点找到盒子的问题。我知道如何做交叉点，所以它只是我感兴趣的树结构。我认为四叉树可能适合，但我不确定它将如何处理在不同节点中复制边界框。

最好是使用某种二叉搜索树，在这里我递归地分割x和y轴（就像中值切割）？

Answer 1

我建议你使用分段树。

看一看这些幻灯片：

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

你特别希望在更高层面解决刺伤查询（幻灯片25）