c++ - 在笛卡尔二维空间的每个象限中找到最近的点

Question

我在 2D 笛卡尔空间 中有 N 个点 加载到 boost:rtree 中。 给定一个不在树中的随机点 P(x,y)，我需要找到一种有效的方法来为 local csys< 生成的四个象限中的每一个确定最近的点/em> 以 P 为中心并与主坐标系平行

如图(上方链接)所示，给定红色点，我需要找到四个紫色点。

我试过这种天真的方法:

namespace bg = boost::geometry;
typedef bg::model::box<point> box;
vector<item> result_s;
vector<item> result_p;

int xres = 10; /*this is a fixed amount that is loosely related to the points distribution*/
int yres = 10; /*as for xres*/
int range = 10;   
int maxp = 30;

/*
* .. filling the tree
*/

box query_box2(point(lat, lon), point(lat-range*yres, lon+range*xres));
rtree.query(bgi::intersects(query_box2) && bgi::nearest(p, maxp), std::back_inserter(result_p));
if(result_p.size()>0) result_s.push_back(result_p[0]);
result_p.clear();

box query_box1(point(lat, lon), point(lat+range*yres, lon+range*xres));
rtree.query(bgi::intersects(query_box1) && bgi::nearest(p, maxp), std::back_inserter(result_p));
if(result_p.size()>0) result_s.push_back(result_p[0]);
result_p.clear();

box query_box3(point(lat, lon), point(lat+range*yres, lon-range*xres));
rtree.query(bgi::intersects(query_box3) && bgi::nearest(p, maxp), std::back_inserter(result_p));
if(result_p.size()>0) result_s.push_back(result_p[0]);
result_p.clear();

box query_box4(point(lat, lon), point(lat-range*yres, lon-range*xres));
rtree.query(bgi::intersects(query_box4) && bgi::nearest(p, maxp), std::back_inserter(result_p));
if(result_p.size()>0) result_s.push_back(result_p[0]);
result_p.clear();

if(result_s.size()>3)
   cout << "OK!" << endl;
else
   cout << "KO" << endl;

但通常以空结果结束(KO)

任何建议或地址将不胜感激。

谢谢。

Answer 1

我会执行一个迭代的nearest 查询。

它将产生按距离升序排序的最近点。

你 can cancel it在所有象限中至少获得 1 分后。

原则上，这种方法的时间复杂度要低得多，因为它只涉及一个查询。

最坏情况下的行为会遍历树中的所有点，例如

• 如果一个象限不包含任何点，或者
• 当一个象限中的所有点实际上都比另一个象限中的最近点更近时。

似乎前者在您的模型中可能是不可能的(？)，而后者在正态分布中在统计学上是不可能的。您必须检查您的域的预期点分布。

或者，这始终适用:测量并比较有效性能