检索设置包含指定点的矩形 [英] Retrieve set of rectangles containing a specified point
问题描述
我无法弄清楚如何在一个表演的方式实现这一点，所以我决定要问你们。
I can't figure out how to implement this in a performing way, so I decided to ask you guys.
我有矩形列表 - 实际大气压只能广场，但我可能要稍后再迁移到矩形，所以我们坚持给他们，并保持它多一点的一般 - 在一个2维空间。每个矩形两点规定，矩形可以重叠，我不在乎所有的太多准备时间，因为长方形的basicly静态的，有一些空间precalculate任何设置的东西（如建筑物的树木，整理，precalculating额外的载体，不管等）。哦，我在JavaScript开发，如果这是任何关注。
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?
线性方法不执行不够好。所以我看的东西，性能比O（n）的更好。我看了一些东西，像包围盒层次结构和类似的事情，但无论我想的是，矩形可以重叠（实际上我想所有的人，如果点位于多个矩形内）似乎永远进入我的路
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.
有没有什么建议？我错过了一些东西明显？是BVH甚至适用于可能重叠的界限？如果是这样，我怎么建立这样一个可能有重叠的树？如果没有，我可以用什么？这不是我关注的重点，如果边界是内，外或不能确定。
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.
如果有人能拿出什么有帮助想了解我是多么愚蠢是使用BVH链接或咆哮，而不是Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem我真的AP preciate了！
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!
编辑：确定，我打了一下周围使用R-树木，这正是我一直在寻找。逸岸我目前使用的RTREE实施 http://stackulator.com/rtree/ 所建议的endy_c。它执行得很好，fullfills我的要求完全。非常感谢您的支持家伙！
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!
推荐答案
您可以看看R-树
也有一个维基，但只能发布一条链路; - ）
there's also a wiki, but can only post one link ;-)
这篇关于检索设置包含指定点的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
