Нахождение ближайшей точки эффективным способом

Question

У меня есть точка в 2d плоскости, например (x0, y0) и набор из n точек (x1, y1) ... (xn, yn), и я хочу найти ближайшую точку к (x0, y0 ) лучше, чем пытаться все точки. Любые решения?

Я также должен сказать, что мои баллы отсортированы следующим образом:

bool less(point a,point b){
  if(a.x!=b.x)
     return a.x<b.x;
  else
     return a.y<b.y;
 }

Answer 1

Использовать квад-дерево для 2D http://en.wikipedia.org/wiki/Quadtree

Answer 2

Диаграмма Вороного предназначена специально для очень быстрого нахождения ближайшей точки. Хотя это довольно сложно реализовать, вы можете найти некоторые существующие библиотеки / реализации.

Существует также возможность многократного деления плоскости на квадраты, таким образом, создается некое дерево, в котором у каждого неконечного узла есть 4 дочерних элемента (верхний правый квадрат, нижний правый квадрат и т. Д.). Затем из четырех квадратов вы найдете тот, в котором находится ваша точка, и продолжите ее рекурсивно. Часто это дает точку достаточно близко, так что вы можете исключить необходимость проверки других квадратов.
Но легко создать «контрпример» для этой стратегии, который приведет к линейному времени.

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

редактировать
Вторая структура называется Quadtree , спасибо VGE за предоставление имени.

Answer 3

Для эффективного поиска ближайшего соседа вам необходимо использовать схему пространственного разделения, например: k d-tree .

Answer 4

Если вы не используете какую-либо древовидную структуру данных, чтобы ограничить диапазон значений, которые вы должны запросить, вам нужно будет проверить каждую точку в диапазоне потенциальных «соседей».Одним из способов ограничения сравнений будет проверка квадрата расстояния от заданной точки для наименьшего значения:

Point myPoint = {x, y};
std::vector<Point> otherPoints; // given list of points to check

struct PointDistance
{
    Point pt;
    float dist;
};

std::vector<PointDistance> squaredDistances(otherPoints.size()); // will be filled in with squared distances

float CalculateDistance(const Point& pt1, const Point& pt2)
{
    float deltaX = pt1.x - pt2.x;
    float deltaY = pt1.y - pt2.y;
    return (deltaX * deltaX) + (deltaY * deltaY);
}

// should be changed to use an algorithm, but for clarity done as a loop here
for (int i = 0; i < otherPoints.size(); ++i)
{
    PointDistance pd;
    pd.pt = otherPoints[i];
    pd.dist = CalculateDistance(myPoint, pd.pt);
    squaredDistances.push_back(pd);
}

bool DistanceLess(const PointDistance& lhs, const PointDistance& rhs)
{
    return lhs.dist < rhs.dist;
}

std::sort(squaredDistances.begin(), squaredDistances.end(), DistanceLess);

// squaredDistances[0].pt will be your closest point.

Answer 5

Особенно хорошим решением является ANN: Библиотека для поиска приблизительных ближайших соседей. Я использовал ее для определения местоположения в триангуляциях.Вы инициализируете структуру данных точками, в моем случае я использовал центральные точки моих треугольников.Затем вы можете перейти в другую точку и получить обратно список приближенных ближайших соседних точек.Даже количество возвращенных точек можно выбрать в качестве параметра.В любом случае ANN была отличной библиотекой для моих целей, я бы посоветовал вам проверить ее.

Удачи!

Answer 6

Если вы создаете набор из N точек, то вместо того, чтобы просто помещать их в набор, вы можете хэшировать и отображать их на основе их линейного расстояния от рассматриваемой точки.Таким образом, точки с одинаковым линейным расстоянием будут в одном ведре.Тогда выбор точки (ей) на основе расстояния будет операцией с постоянным временем.