Hacker News Reader

Comment by abainbridge | Hacker News Reader

> 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?

View on HN

The 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

Basically, 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-algorithm...

Yes 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.

Reply on news.ycombinator.com