c++ - 如何制作一个 boost 多索引复合范围语句，相当于 where x AND y？

Question

我有一组在二维空间中任意分布的 N 点。每个点都有一个关联的 x y 坐标。从任何一点开始，我都需要在给定距离 r 内找到一组其他点。如果我不关心时间，我会将所有内容添加到 sqlite 数据库，然后运行 ​​select * from table where x between x1 and x2 and y between y1 and y2 但基于我读过的内容，数据库的开销对于我的用例来说是高得惊人的(N~1e7，每个点都需要计算)。我可以获得具有 x 条件或 y 条件的一系列点，但我不知道获得它们交集的优雅方法。解决这个问题的最佳方法是什么？获取两个范围并应用一些交集算法？只获取一个范围并遍历，只保留相关点？或者有什么方法可以使用 boost 多索引进行复合选择？

这是一个 MWE，它使用均匀随机点定义和填充多索引，并通过 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 可能不是这个问题的正确容器:考虑使用 spatial index structure , 其中Boost.Geometry提供 some .