Find the nearest point in each quadrant in a cartesian 2D space

Question

I have N points in a 2D cartesian space loaded in a boost:rtree. Given a random point P(x,y) not in the tree, I need to find an effective way to identify the nearest point for each of the four quadrant of generated by the local csys centered in P and parallel to the main csys

As shown in the image (linked above), given the red point I need to find the four purple points.

I tried this naive approach:


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;

but often it end up with an empty result (KO)

Any suggestion or address will be very appreciated.

Tnx.

Shouldn't the x- and y- values of `box::min_corner` be smaller than those of `box::max_corner`? — Albjenow, Oct 01 '19 at 10:52
@Albjenow it worked, tnx a lot. Hope to find a more efficient way than my "naive" code. — Aquilante, Oct 01 '19 at 15:23

sehe · Answer 1 · 2019-10-04T16:21:27.123

I would do an iterated nearest query.

It will produce nearest points ordered by distance ascending.

You can cancel it after you received at least 1 point in all quadrants.

In principle the time complexity of this approach is MUCH lower because it involves only a single query.

Worst case behaviour would iterate all points in the tree e.g.

if one quadrant doesn't contain any points, or
when all the points in one quadrant are actually closer than the closest point in another quadrant.

Seems like the former might not be possible in your model (?) and the latter is statistically unlikely with normal distributions. You'd have to check your domains expected point distributions.

Or, and this always applies: MEASURE and compare the effective performance

Thanks @sehe. I ended up with the solution you suggested. There are no big differences in performances. The only reason that pushed me to make this choice is that the points are oddly distributed and this solution is much tolerant to non uniform distribution. Still looking fore something more robust. — Aquilante, Oct 07 '19 at 12:30

score 0 · Answer 2 · answered Oct 18 '19 at 19:56

Use a modified distance function. More precisely, use four.

The main idea is to use a distance such that

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

If you search for the nearest point with this distance, it must be in the top right quadrant.

You'll need to extend this logic to minDist when searching the tree.

The benefit is that it can stop searching a quadrant when it has found a point. Pages that overlap the "axes" may be expanded twice though.

Find the nearest point in each quadrant in a cartesian 2D space

2 Answers2