R* tree

[emirpasic]

One of the hardest data structures to implement, especially due to the splitting function, but is frequently used throughout GIS.

Vote if you'd like to see this in GoDS.

Notes:

http://www.boost.org/doc/libs/1_58_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html

[emirpasic]

Unfortunately, I do not have the time to implement this complex structure given more than 4 years have passed. If you ever come across this comment and wish to do so, I would be more than happy to assist.

I would suggest starting from the battle-tested postGIS implementation of the spatial index which uses an R-Tree and should be easy to port into Golang and exclude the extra bits.