All geek questions in one place

Find a rectangle in 2d space

I have a set of rectangles of various sizes in a 2D space. The number of rectangles can change dynamically from 10 to 100,000, their position, as well as their size, are often updated.

What spatial structure would you suggest finding a rectangle at a given point (x, y)? Assuming that the search operation is also performed very often (for example, when moving the mouse). If you could give a link to various spatial indexing algorithms or compare their search / build / update results here - that would be great.

+4
source share
2 answers

I would suggest R-Tree . It is intended primarily for rectangles (or cubes with a zero axis).

+2
source

Use the quadrant ( http://en.wikipedia.org/wiki/Quadtree ).

Identify all possible X and Y values ​​at which the rectangle begins and ends. Then build a quadrant on these values. In each sheet of the quadrant, save which rectangles overlap the coordinate ranges of the sheet. Finding which rectangles overlap is simply a search for the sheet containing the coordinate.

0
source

Source: https://habr.com/ru/post/1413451/

More articles:


All Articles