3 ms·
> Enables fast spatial queries on a very large number of objects Can someone explain that? I assume the problem is something like, "user clicks on 2D map, find
by abainbridge 8y ago
> Enables fast spatial queries on a very large number of objects
Can someone explain that? I assume the problem is something like, "user clicks on 2D map, find which objects are near the click". A naive solution might store the objects in an array sorted by X coordinate. The problem there is that the search for objects near (x,y) would have discard many objects that were far away on the Y axis. Somehow this thing solves that problem?
- laszlokorte 8y agoThe readme says it uses an R-tree.[0] As the wikipedia article explains all the objects are grouped so that near by objects are put in the same group and for each group a bounding box is stored. When querying the the structure for a given position you can discard all groups that to not intersect your given position/range. [0] https://en.wikipedia.org/wiki/R-tree https://en.wikipedia.org/wiki/R-tree
- laythea 8y agoYes indeed. Eg a camera location coordinate can be thrown at these kinds of things (this is 2d, eg quadtrees, but similar things exist for 3d also, see octtrees), and it return all the 3d objects in that space (out of a huge number of objects in the entire "universe"). And then the program processes that reduced list of objects. I think of these as like a prefilter.
- mourner 8y agoBasically, yes. I wrote a long article about this [1] which goes into depth on how algorithms like this work — hope it helps! [1] https://blog.mapbox.com/a-dive-into-spatial-search-algorithms-ebd0c5e39d2a https://blog.mapbox.com/a-dive-into-spatial-search-algorithm...