efficient C++ template implementation for 2D range queries

Question

I need to store custom point objects (getX() and getY() are provided) in an efficient way to perform range queries. So i was looking for templated implementations of quadtree, kd-tree or similar. For example like this: https://code.google.com/p/kche-tree/ (but this only seems to work with primitive types...?)

Are there suggestions? Or would i need to implement it myself? (open source license required)

Thanks!

Answer 1

Try to use boost. Boost are usually pretty good C++ libraries.

And Boost Geometry has and R-tree for nearest neighbor search.

Answer 2

Check this out https://compilr.com/cobalthex/quadtree/main.cpp It's also what I am looking for. I guess the code is opensource and you are able to reuse and modify it.

All you need is the Quadtree.h and Quadtree.cpp. Modify the XY point to the struct that you see suitable for your usage.

Hope this helps!