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

Question

3

我创建了一个函数，它会遍历一个2D边界框的列表，并找到包含给定2D点的边界框。不幸的是，这个过程非常缓慢，因此我正在寻找一种使用某种树结构进行优化的方法。

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

最好使用某种二叉搜索树，其中我可以递归地分割x和y轴（类似于中位数切割）吗？

- LoweredTone

会做的，这是我的第一个问题，所以没有意识到！ - LoweredTone

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Juan Leni · Accepted Answer

我建议您使用线段树。

请查看这些幻灯片：

您特别寻求解决高维度刺穿查询的方案（幻灯片25）。