Найти ближайшую точку в каждом квадранте в декартовом двумерном пространстве - PullRequest
Новая
       59

Найти ближайшую точку в каждом квадранте в декартовом двумерном пространстве

1 голос
/ 01 октября 2019

У меня N точек в 2D декартовом пространстве , загруженных в усиление: rtree . Учитывая случайную точку P (x, y) , отсутствующую в дереве, мне нужно найти эффективный способ определения ближайшей точки для каждого из четырех квадрантов, генерируемых локальным csys по центру P и параллельно основному csys

enter image description here

Как показано на рисунке (ссылка выше), учитывая красную точку, мне нужно найтичетыре фиолетовых точки.

Я попробовал этот наивный подход: 


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)

Любое предложение или адрес будут оченьприветствуется.

Tnx.

Ответы [ 2 ]

0 голосов
/ 18 октября 2019

Используйте модифицированную функцию расстояния. Точнее, используйте четыре.

Основная идея состоит в том, чтобы использовать расстояние такое, чтобы 

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 при поиске дерева.

Преимущество заключается в том, что он может прекратить поиск квадранта, когда найдет точку. Хотя страницы, которые перекрывают «оси», могут быть развернуты дважды.

0 голосов
/ 04 октября 2019

Я бы сделал повторный запрос nearest.

Он выдаст ближайшие точки, упорядоченные по возрастанию расстояния.

Вы можете отменить его после того, как вы получили хотя бы 1 очко во всех квадрантах.

ВВ принципе, временная сложность этого подхода НАМНОГО ниже, потому что он включает в себя только один запрос.

В худшем случае поведение будет повторять все точки дерева, например

  • , если один квадрант несодержат любые точки, или
  • , когда все точки в одном квадранте фактически ближе, чем ближайшая точка в другом квадранте.

Похоже, что первое может быть невозможно в вашей модели (?) и последнее статистически маловероятно при нормальных распределениях. Вам нужно будет проверить ожидаемое распределение баллов в ваших доменах.

Или, и это всегда применимо: ИЗМЕРИТЬ и сравнить эффективную производительность

...