检索包含指定点的矩形集
我不知道如何以表演的方式实现这一点，所以我决定问你们。
我有一个矩形列表 - 实际上只有 atm 正方形，但稍后我可能必须迁移到矩形，所以让我们坚持使用它们并使其更通用 - 在二维空间中。每个矩形由两个点指定，矩形可以重叠，我不太关心设置时间，因为矩形基本上是静态的，并且有一些空间可以预先计算任何设置内容（例如构建树，排序，预先计算附加向量，无论如何等等）。哦，如果有任何问题的话，我正在使用 JavaScript 进行开发。
对于我的实际问题：给定一个点，如何获得包含该点的所有矩形的集合？
线性方法的性能不够好。所以我寻找比 O(n) 性能更好的东西。我读了一些东西，比如边界体积层次结构和类似的东西，但无论我尝试什么，矩形可以重叠（而且我实际上想要得到所有它们，如果点位于多个矩形内）似乎总是妨碍我。
有什么建议吗？我错过了一些明显的事情吗？ BVH 是否适用于可能重叠的边界？如果是这样，我如何构建这样一个可能重叠的树？如果没有，我还能用什么？边界是内部的、外部的还是不确定的，我并不关心。
如果有人能提出任何有用的东西，比如链接或咆哮我使用 BVH 而不是 Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem 是多么愚蠢，我真的很感激！
编辑： 好吧，我玩了一下 R-Trees，这正是我想要的。事实上，我目前正在按照 endy_c 的建议使用 RTree 实现 http://stackulator.com/rtree/ 。它的性能非常好，完全满足我的要求。非常感谢各位的支持！
I can't figure out how to implement this in a performing way, so I decided to ask you guys.
I have a list of rectangles - actually atm only squares, but I might have to migrate to rectangles later, so let's stick to them and keep it a bit more general - in a 2 dimensional space. Each rectangle is specified by two points, rectangles can overlap and I don't care all too much about setup time, because the rectangles are basicly static and there's some room for precalculate any setup stuff (like building trees, sorting, precalculating additional vectors, whatever etc). Oh I am developing in JavaScript if this is of any concern.
To my actual question: given a point, how do I get a set of all rectangles that include that point?
Linear approaches do not perform well enough. So I look for something that performs better than O(n). I read some stuff, like on Bounding Volume Hierarchies and similar things, but whatever I tried the fact that rectangles can overlap (and I actually want to get all of them, if the point lies within multiple rectangles) seems to always get into my way.
Are there any suggestions? Have I missed something obvious? Are BVH even applicable to possibly overlapping bounds? If so, how do I build such a possibly overlapping tree? If not, what else could I use? It is of no concern to me if borders are inside, outside or not determined.
If someone could come up with anything helpfull like a link or a rant on how stupid I am to use BVH and not Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem I'd really appreciate it!
Edit: Ok, I played around a bit with R-Trees and this is exactly what I was looking for. Infact I am currently using the RTree implementation http://stackulator.com/rtree/ as suggested by endy_c. It performs really well and fullfills my requirements entirely. Thanks alot for your support guys!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
你可以看看 R-Trees
Java code
还有一个 wiki，但只能发布一个链接；- ）
You could look at R-Trees
Java code
there's also a wiki, but can only post one link ;-)
您可以将空间划分为网格，并且对于每个网格单元都有一个至少部分存在于该网格中的矩形（或矩形标识符）列表。仅在相应网格的单元格中搜索矩形。复杂度应该是 O(sqrt(n))。
另一种方法是维护四个 x1、y1、x2、y2 值的排序数组，并在这 4 个数组中对您的点进行二分搜索。每次搜索的结果是一组候选矩形，最终结果是这 4 组矩形的交集。根据集合交集的实现方式，这应该比 O(n) 更高效。
You can divide the space into grid, and for each grid cell have a list of rectangles (or rectangle identifiers) that exist at least partially in that grid. Search for rectangles only in corresponding grid's cell. The complexity should be O(sqrt(n)).
Another approach is to maintain four sorted arrays of x1,y1,x2,y2 values, and binary search your point within those 4 arrays. The result of each search is a set of rectangle candidates, and the final result is intersection of those 4 sets. Depending on how set intersection is implemented this should be efficient than O(n).