Question

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!

Answer 1

You could look at R-Trees

Java code

there s also a wiki, but can only post one link ;-)

Answer 2

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).

友情链接