2

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

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

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

4

1 回答 1

1

我建议您使用分段树。

看看这些幻灯片：

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

您正在特别寻找解决更高维度查询的解决方案（幻灯片 25）

于 2014-11-20T17:35:46.470 回答