Dan*_*lig 3 algorithm search geometry point-in-polygon
我无法弄清楚如何以表演方式实现这一点,所以我决定问你们.
我有一个矩形列表 - 实际上atm只有正方形,但我可能不得不稍后迁移到矩形,所以让我们坚持它们并保持它更一般 - 在二维空间中.每个矩形由两个点指定,矩形可以重叠,我不太关心设置时间,因为矩形基本上是静态的,并且有一些预先计算任何设置内容的空间(如构建树,排序,预先计算其他向量,等等).哦,如果有任何问题,我正在开发JavaScript.
对于我的实际问题:给出一个观点,我如何得到一组包含该点的所有矩形？
线性方法表现不佳.所以我寻找比O(n)更好的东西.我读了一些东西,比如在Bounding Volume Hierarchies和类似的东西上,但无论我尝试了矩形可以重叠的事实(我实际上想要得到所有这些,如果点在多个矩形内)似乎总是进入我的方式.
有什么建议吗？我错过了一些明显的事吗？BVH是否适用于可能重叠的边界？如果是这样,我如何构建这样一个可能重叠的树？如果没有,我还能用什么？如果边界在内部,外部或未确定,我不关心.
如果有人能想出任何有用的东西,比如链接或咆哮我是多么愚蠢的使用BVH而不是Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem我真的很感激!
编辑:好的,我和R-Trees玩了一下,这正是我想要的.事实上,我正在使用endy_c 建议的RTree实现http://stackulator.com/rtree/.它表现得非常好,完全满足了我的要求.非常感谢您的支持!