Алгоритм наименьшего расстояния между точками

Question

Учитывая набор точек на плоскости, найдите самый короткий отрезок прямой, образованный любыми двумя из этих точек.

Как я могу это сделать? Тривиальный способ, очевидно, состоит в том, чтобы рассчитать каждое расстояние, но мне нужен другой алгоритм для сравнения.

Answer 1

http://en.wikipedia.org/wiki/Closest_pair_of_points

Проблема может быть решена за O (n log n) с использованием рекурсивного подхода «разделяй и властвуй», например, следующим образом:

• Сортировка точек по координате х
• Разбить множество точек на два подмножества одинакового размера вертикальной линией x = xmid
• Решить проблему рекурсивно в левом и правом подмножествах. Это даст минимальные расстояния слева и справа dLmin и dRmin соответственно.
• Найдите минимальное расстояние dLRmin между парой точек, в которой одна точка лежит слева от делительной вертикали, а вторая точка - справа.
• Окончательный ответ - минимум среди dLmin, dRmin и dLRmin.

Answer 2

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

Answer 3

Одной из возможностей может быть сортировка точек по их координатам X (или Y - на самом деле не имеет значения, какая, просто быть последовательной). Затем вы можете использовать это, чтобы устранить сравнения со многими другими пунктами. Когда вы смотрите на расстояние между точкой [i] и точкой [j], если только расстояние X больше вашего текущего кратчайшего расстояния, то точка [j + 1] ... точка [N] может быть удалена как хорошо (при условии i<j - если j<i, то это точка [0] ... точка [i], которые исключаются).

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

Answer 4

Вы можете извлечь ближайшую пару в линейном времени из Триангуляции Делоне и в режиме разговора из Диаграмма Вороного .

Answer 5

Существует стандартный алгоритм для этой проблемы, здесь вы можете найти его: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html

А вот моя реализация этого алгоритма, извините, что без комментариев:

    static long distSq(Point a, Point b) {
    return ((long) (a.x - b.x) * (long) (a.x - b.x) + (long) (a.y - b.y) * (long) (a.y - b.y));
}

static long ccw(Point p1, Point p2, Point p3) {
    return (long) (p2.x - p1.x) * (long) (p3.y - p1.y) - (long) (p2.y - p1.y) * (long) (p3.x - p1.x);
}

static List<Point> convexHull(List<Point> P) {

    if (P.size() < 3) {
        //WTF
        return null;
    }

    int k = 0;

    for (int i = 0; i < P.size(); i++) {
        if (P.get(i).y < P.get(k).y || (P.get(i).y == P.get(k).y && P.get(i).x < P.get(k).x)) {
            k = i;
        }
    }

    Collections.swap(P, k, P.size() - 1);

    final Point o = P.get(P.size() - 1);
    P.remove(P.size() - 1);


    Collections.sort(P, new Comparator() {

        public int compare(Object o1, Object o2) {
            Point a = (Point) o1;
            Point b = (Point) o2;

            long t1 = (long) (a.y - o.y) * (long) (b.x - o.x) - (long) (a.x - o.x) * (long) (b.y - o.y);

            if (t1 == 0) {
                long tt = distSq(o, a);
                tt -= distSq(o, b);
                if (tt > 0) {
                    return 1;
                } else if (tt < 0) {
                    return -1;
                }
                return 0;

            }
            if (t1 < 0) {
                return -1;
            }
            return 1;

        }
    });



    List<Point> hull = new ArrayList<Point>();
    hull.add(o);
    hull.add(P.get(0));


    for (int i = 1; i < P.size(); i++) {
        while (hull.size() >= 2 &&
                ccw(hull.get(hull.size() - 2), hull.get(hull.size() - 1), P.get(i)) <= 0) {
            hull.remove(hull.size() - 1);
        }
        hull.add(P.get(i));
    }

    return hull;
}

static long nearestPoints(List<Point> P, int l, int r) {


    if (r - l == P.size()) {

        Collections.sort(P, new Comparator() {

            public int compare(Object o1, Object o2) {
                int t = ((Point) o1).x - ((Point) o2).x;
                if (t == 0) {
                    return ((Point) o1).y - ((Point) o2).y;
                }
                return t;
            }
        });
    }

    if (r - l <= 100) {
        long ret = distSq(P.get(l), P.get(l + 1));
        for (int i = l; i < r; i++) {
            for (int j = i + 1; j < r; j++) {
                ret = Math.min(ret, distSq(P.get(i), P.get(j)));
            }
        }
        return ret;

    }

    int c = (l + r) / 2;
    long lD = nearestPoints(P, l, c);
    long lR = nearestPoints(P, c + 1, r);
    long ret = Math.min(lD, lR);
    Set<Point> set = new TreeSet<Point>(new Comparator<Point>() {

        public int compare(Point o1, Point o2) {
            int t = o1.y - o2.y;
            if (t == 0) {
                return o1.x - o2.x;
            }
            return t;
        }
    });
    for (int i = l; i < r; i++) {
        set.add(P.get(i));
    }

    int x = P.get(c).x;

    double theta = Math.sqrt(ret);

    Point[] Q = set.toArray(new Point[0]);
    Point[] T = new Point[Q.length];
    int pos = 0;
    for (int i = 0; i < Q.length; i++) {
        if (Q[i].x - x + 1 > theta) {
            continue;
        }
        T[pos++] = Q[i];
    }

    for (int i = 0; i < pos; i++) {
        for (int j = 1; j < 7 && i + j < pos; j++) {
            ret = Math.min(ret, distSq(T[i], T[j + i]));
        }
    }
    return ret;
}

Answer 6

Из вашего вопроса не ясно, ищете ли вы расстояние сегмента или сам сегмент. Предполагая, что вы ищете расстояние (сегмент в простой модификации, когда вы знаете, какие две точки имеют минимальное расстояние), учитывая 5 точек, пронумерованных от 1 до 5, вам нужно

compare 1 with 2,3,4,5, then 
compare 2, with 3,4,5, then 
compare 3 with 4,5, then 
compare 4 with 5.

Если я не ошибаюсь, учитывая коммутативность расстояния, вам не нужно проводить другие сравнения. В питоне может звучать как-то

import numpy as np
def find_min_distance_of_a_cloud(cloud):
        """
        Given a cloud of points in the n-dim space, provides the minimal distance.
        :param cloud: list of nX1-d vectors, as ndarray.
        :return:
        """
        dist_min = None
        for i, p_i in enumerate(cloud[:-1]):
            new_dist_min = np.min([np.linalg.norm(p_i - p_j) for p_j in cloud[(i + 1):]])
            if dist_min is None or dist_min > new_dist_min:
                dist_min = new_dist_min

        return dist_min

Это можно проверить с помощью следующего кода:

from nose.tools import assert_equal

def test_find_min_distance_of_a_cloud_1pt():
    cloud = [np.array((1, 1, 1)), np.array((0, 0, 0))]
    min_out = find_min_distance_of_a_cloud(cloud)
    assert_equal(min_out, np.sqrt(3))


def test_find_min_distance_of_a_cloud_5pt():
    cloud = [np.array((0, 0, 0)),
             np.array((1, 1, 0)),
             np.array((2, 1, 4)),
             np.array((3, 4, 4)),
             np.array((5, 3, 4))]
    min_out = find_min_distance_of_a_cloud(cloud)
    assert_equal(min_out, np.sqrt(2))

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