1. I have Grid of unlimited size (I don't and can't know what its size)
  2. There is Object that should be placed on the grid, every object have hes stream distance (in other words: range, default: 300) and 2D coordinates (position)
  3. There is function find that 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?

My way

  1. 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).
  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.
  3. Every time object inserted check what cells does the object fit and adding the object to the cell object list.
  4. When function find get called he search's only in the cell of the given coordinate.

    [ Assume triangle is an object ]

    enter image description here

Similar Questions


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.