1

我有一组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;
}
4

1 回答 1

2

Boost.MultiIndex 可能不是这个问题的正确容器：考虑使用空间索引结构，其中Boost.Geometry提供了一些。

于 2014-01-19T13:24:44.617 回答