Алгоритм ближайшей пары точек - PullRequest
Новая
       25

Алгоритм ближайшей пары точек

5 голосов
/ 23 февраля 2012

Я пытаюсь реализовать более простую версию этого алгоритма, но она работает лучше, чем квадратичный алгоритм. Моя идея состоит в том, чтобы отсортировать точки только по координате х и попытаться решить их оттуда. После того, как я отсортировал массив точек по координате х, я хочу перебрать массив и в основном пропустить точки, расстояние которых больше, чем первые две точки, которые я взял.

Например, мой currentminDist = x;

Если две пары точек, на которые я смотрю, имеют расстояние> x (только по его координате x dist), я игнорирую точку и перемещаюсь за ней в массиве.

У меня нет идеи, но я застрял на том, как на самом деле реализовать это (особенно часть условия). У меня есть функция, которая возвращает мне расстояние между двумя точками на основе их координаты х.

Я запутался в том, как на самом деле написать мои условия для моего цикла, так как я хочу игнорировать точку, если расстояние оказывается слишком большим, и все же заполнить мой массив, который будет содержать ответы для ближайших точек для каждого i текущая точка, на которую я смотрю).

Любые советы или указания будут с благодарностью. Я не очень хорошо разбираюсь в алгоритмах кодирования, поэтому это довольно расстраивает.

Вот часть моего кода: 

for (i = 0; i < numofmypoints; i++)
        {
            for (int j = i + 1; (j < numpofmypoints) && ((inputpoints[j].x - inputpoints[i].x) < currbest); j++ )
            {
                currdist = Auxilary.distbyX(inputpoints[i],inputpoints[j]);

                if (currdist < bestdist) 
                {
                 closest[i] = j;
                 bestdist = currdist;

                }
            }
        }

distbyX - моя функция, которая просто возвращает расстояние между двумя точками.

Спасибо!

1 Ответ

4 голосов
/ 23 февраля 2012

Быстрый алгоритм с использованием KD-дерева
Этот алгоритм создает kd-дерево и затем находит ближайшую пару для каждой точки.Создание дерева kd - это O (n log 2 n), а поиск ближайшего соседа точки - O (logn).Кредит должен идти на Википедию , которая в одной статье объясняет, как создавать kd-деревья, а также как использовать их для поиска ближайшего соседа.Исправьте код в вопросе
Если вы действительно не беспокоитесь о сложности, единственная проблема с вашим кодом заключается в том, что вы смотрите вперед, а не назад.Просто продублируйте внутренний цикл и заставьте j перейти от (i - 1) к 0: 

Point[] points = sort(input());
int[] closest = new int[points.length];

for (int i = 0; i < points.length; i++)
{
    double bestdist = Double.POSITIVE_INFINITY;

    for (int j = i + 1; (j < points.length) && ((points[j].x - points[i].x) < bestdist); j++ )
    {
        double currdist = dist(points[i], points[j]);

        if (currdist < bestdist)
        {
            closest[i] = j;
            bestdist = currdist;
        }
    }
    for (int j = i - 1; (j >= 0) && ((points[i].x - points[j].x) < bestdist); j-- )
    {
        double currdist = dist(points[i], points[j]);

        if (currdist < bestdist)
        {
            closest[i] = j;
            bestdist = currdist;
        }
    }
}
...