- I have
Gridof unlimited size (I don't and can't know what its size)
- There is
Objectthat should be placed on the grid, every object have hes stream distance (in other words: range, default: 300) and 2D coordinates (position)
- There is function
findthat takes 2D coordinates and should return what object are shown
It seems that R-tree is the answer to my question, is there any explanation about how exactly the algorithm works?
- Dividing the cell sizes to levels, level 1 is 600x600 (2 times bigger than default stream distance), level 2 is 1200x1200 and so on... (every time the cell sizes is multiplied by 2).
- Associate the objects in the corresponding cell by multiplying the stream distance by 2 and round to the next multiple of 600, for example: stream distance is 450, multiplying it by 2 gives 900, rounding it to the next multiple of 600 gives 1200.
- Every time object inserted check what cells does the object fit and adding the object to the cell object list.
findget called he search's only in the cell of the given coordinate.
[ Assume triangle is an object ]