我不知道如何以一种表演的方式来实现它，所以我决定问你们。

我有一个矩形列表-
实际上只有atm正方形，但是稍后可能需要迁移到矩形，所以让我们坚持下去，并在二维空间中更笼统一些。每个矩形都由两个点指定，矩形可以重叠，并且我不太在意设置时间，因为矩形基本上是静态的，并且有一些空间可以预先计算任何设置内容（例如，构建树，排序，预先计算其他矢量，等等）。哦，如果有任何问题，我正在用JavaScript开发。

对于我的实际问题：给定一个点，我如何得到一组包含该点的所有矩形？

线性方法的表现不够好。因此，我寻找一种性能优于O（n）的产品。我读了一些东西，例如关于边界体积层次结构之类的东西，但是我尝试尝试矩形可以重叠的事实（如果点位于多个矩形内，我实际上想要得到所有矩形）似乎总是会妨碍我。

有什么建议吗？我是否错过了明显的事情？BVH是否甚至适用于可能重叠的边界？如果是这样，我如何构建这样一个可能重叠的树？如果没有，我还能使用什么？对于边界是内部，外部还是未确定边界，我都不关心。

如果有人能提出一些有用的建议，例如链接或关于我使用BVH的愚蠢而不是Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem的愚蠢之举，我将不胜感激！

编辑： 好的，我在R-Trees上玩了一些，这正是我想要的。实际上，我目前正在使用endy_c
建议的RTree实现http://stackulator.com/rtree/。它的性能非常好，完全满足了我的要求。非常感谢您的支持！