Working example of using Boost Geometry for k-nearest neighbors search with an R-tree

gistfile1.txt

/* compile with:
clang++ -std=c++2a -I . -Ofast -march=native rtree_nearest_neighbor_test.cpp -o rtree_nearest_neighbor_test

adjust the -I parameter depending on where boost is located.
*/

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/foreach.hpp>

#include <random>
#include <vector>
#include <chrono>
#include <iostream>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

typedef bg::model::point<double, 2, bg::cs::cartesian> point;
typedef std::pair<point, unsigned> value;

int main(int argc, char *argv[])
{
	if (argc == 1) {
		std::cerr << "Provide a parameter" << std::endl;
		return 1;
	}

	int n = std::atoi(argv[1]);

	std::random_device rd;
	std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(-10.0, 10.0);
	bgi::rtree< value, bgi::quadratic<16> > rtree;	

	// create some values
	for ( int i = 0 ; i < n ; ++i )
	{
	    // insert new value
	    double x = dis(gen);
	    double y = dis(gen);
	    rtree.insert(std::make_pair(point(x, y), i));
	}

	auto start = std::chrono::high_resolution_clock::now();
	std::vector<value> result_n;
	result_n.reserve(15);
	rtree.query(bgi::nearest(point(0, 0), 15), std::back_inserter(result_n));
	auto end = std::chrono::high_resolution_clock::now();
	std::chrono::microseconds elapsed_microseconds = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

	std::chrono::duration<double> diff = end -start;
	std::cout << "knn query point:" << std::endl;
	std::cout << bg::wkt<point>(point(0, 0)) << std::endl;
	std::cout << elapsed_microseconds.count() << "us\n";
	std::cout << "knn query result:" << std::endl;
	BOOST_FOREACH(value const& v, result_n)
	    std::cout << bg::wkt<point>(v.first) << " - " << v.second << std::endl;
}