How to make a boost multi-index compound range statement, equivalent of where x AND y?

Question

I have a set of N points spread out arbitrarily in 2D space. Each point has an associated x y coordinate. From any point, I need to find a set of other points within a given distance r from it. If I wasn't concerned about time I would add everything to an sqlite db and just run select * from table where x between x1 and x2 and y between y1 and y2 but based on what I've read, the overhead of the db will be prohibitive for my use case (N~1e7, every point needs to be calculated). I can get a range of points with an x condition or a y condition but I don't know of an elegant way to get their intersection. What's the best way to solve this? Get two ranges and apply some intersection algorithm? Just get one range and iterate through, only keeping the relevant points? Or is there some way to do a compound select with boost multi-index?

Here is a MWE that defines and populates the multi-index with uniformly random points and "queries" a random point by x.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <random>
#include <chrono>

using boost::multi_index_container;
using namespace boost::multi_index;

struct nodePosition
{
    int id;
    double x;
    double y;
    nodePosition(int id_, double x_, double y_):id(id_),x(x_),y(y_){}

    friend std::ostream& operator<<(std::ostream& os,const nodePosition& np)
    {
        os<<np.id<<"\t"<<np.x<<"\t"<<np.y<<std::endl;
        return os;
    }

};

struct id{};
struct x{};
struct y{};

typedef multi_index_container<
    nodePosition,
    indexed_by<
        ordered_unique<
            tag<id>, BOOST_MULTI_INDEX_MEMBER(nodePosition,int,id)>,
        ordered_non_unique<
            tag<x>, BOOST_MULTI_INDEX_MEMBER(nodePosition,double,x)>,
        ordered_non_unique<
            tag<y>, BOOST_MULTI_INDEX_MEMBER(nodePosition,double,y)> >
> node_set;

unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
std::default_random_engine en(seed1);
std::uniform_real_distribution<double> rf(0.0,1.0);


int main(){
 node_set ns;
 int N=1000;
 double r=0.01;
 std::uniform_int_distribution<int> ri(0,N);
 for(int i=0; i<N; ++i){
     ns.insert(nodePosition(i,rf(en),rf(en)));
 }
 int ind = ri(en);
 auto it=ns.get<id>().find(ind);
 std::cout<<*it;
 auto itx2=ns.get<x>().upper_bound(it->x+r);
 auto itx1=ns.get<x>().lower_bound(it->x-r);
 for (auto it_=itx1; it_!=itx2; ++it_){
     std::cout<<*it_;
 }
 return 0;
}

Answer 1

Boost.MultiIndex is probably not the right container for this problem: consider using a spatial index structure, of which Boost.Geometry provides some.