我不知道如何以表演的方式实现这一点，所以我决定问你们。
我有一个矩形列表 - 实际上只是 atm 正方形，但稍后我可能必须迁移到矩形，所以让我们坚持使用它们并使其更通用 - 在二维空间中。每个矩形由两个点指定，矩形可以重叠，我不太关心设置时间，因为矩形基本上是静态的，并且有一些空间可以预先计算任何设置内容（例如构建树，排序，预先计算附加向量，无论如何等等）。哦，如果有任何问题的话，我正在使用 JavaScript 进行开发。
对于我的实际问题：给定一个点，如何获得包含该点的所有矩形的集合？
线性方法的性能不够好。所以我寻找比 O(n) 性能更好的东西。我读了一些东西，比如边界体积层次结构和类似的东西，但无论我尝试什么，矩形可以重叠（而且我实际上想要得到所有它们，如果点位于多个矩形内）似乎总是妨碍我。
有什么建议吗？我错过了一些明显的事情吗？ BVH 是否适用于可能重叠的边界？如果是这样，我如何构建这样一个可能重叠的树？如果没有，我还能用什么？边界是内部的、外部的还是不确定的，我并不关心。
如果有人能提出任何有用的东西，比如链接或咆哮我使用 BVH 而不是 Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem 是多么愚蠢，我真的很感激！
Edit:好吧，我玩了一下 R-Trees，这正是我想要的。事实上我目前正在使用 RTree 实现http://stackulator.com/rtree/正如 endy_c 所建议的。它的性能非常好，完全满足您的要求。非常感谢各位的支持！
你可以看看 R-Trees
Java代码
还有一个 wiki，但只能发布一个链接；-)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
