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

问题描述

我在boost:rtree中加载的二维笛卡尔空间中有N 个点。给定一个不在树中的随机点P(x,y) ，我需要找到一种有效的方法来识别由以 P 为中心并与主 csys 平行的本地 csys生成的四个象限中的每一个的最近点

如图所示（上面链接），给定红点我需要找到四个紫色点。

我尝试了这种天真的方法：


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）

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

肿瘤坏死因子。

标签： c++boostr-tree

使用修改后的距离函数。更准确地说，使用四个。

主要思想是使用这样的距离

d(v1,v2) = infinity if v2.x < v1.x
d(v1,v2) = infinity if v2.y < v1.y
d(v1,v2) = (v1.x-v2.x)²+(v1.y-v2.y)² otherwise

如果你用这个距离搜索最近的点，它必须在右上象限。

搜索树时，您需要将此逻辑扩展到 minDist。

好处是它可以在找到一个点时停止搜索象限。但是，与“轴”重叠的页面可能会扩展两次。

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

问题描述

解决方案

推荐阅读