CODEWITHSUNDEEP
performancealgorithmgeometryspatial-index
CuriousG
CuriousG

Reputation: 327

Find rectangle in 2d space

I have set of rectangles of various sizes in 2D space. Number of rectangles may be changed dynamically from 10 to 100 000, their position, as well as their sizes are often updated.

Which spatial structure would you recommend to find rectangle at given point (x,y)? Assuming that search operation also performed very often (on mouse move for example). If you could give a reference to various spatial indexing algorithms comparison or compare their search/build/update performance here - that would be lovely.

Upvotes: 4

Views: 1548

Answers (2)

Juraj Blaho
Juraj Blaho

Reputation: 13451

I would suggest R-Tree. It is primarily designed for rectangles (or N-dimensional axis aligned cubes).

Upvotes: 2

Patrick
Patrick

Reputation: 23619

Use a quadtree (http://en.wikipedia.org/wiki/Quadtree).

Determine all possible X and Y values at which rectangles start and end. Then build a quadtree upon these values. In each leaf of the quadtree, store which rectangles overlap with the coordinate-ranges of the leaf. Finding which rectangles overlap is then just a matter of finding the leaf containing the coordinate.

Upvotes: 0

Related Questions