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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

http://blogs.mathworks.com/videos/2008/06/02/matlab-puzzler-finding-the-two-closest-points/

Это целая большая куча различных решений. Спрячься, чтобы увидеть, сколько способов есть один и тот же ответ.

Answer 4

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

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

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

Eсть относительно простой алгоритм линейной развертки, который может найти ближайшую пару точек в O (nlogn) времени. У этого article есть краткое объяснение.

Answer 7

Вы можете извлечь ближайшую пару в линейном времени от Delaunay triangulation и, наоборот, от Voronoi diagram.

Answer 8

С вашего вопроса неясно, если вы ищете расстояние от сегмента или самого сегмента. Предполагая, что вы ищете расстояние (участок в той простой модификации, как только вы знаете, которые являются две точек, расстояние которых минимально), с учетом 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)) 

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