Учитывая множество точек на плоскости, найдите кратчайший отрезок, образованный любыми двумя из этих точек.
Как я могу это сделать? Тривиальный путь, очевидно, заключается в вычислении каждого расстояния, но мне нужен другой алгоритм для сравнения.
Наименьшее расстояние между точками алгоритма
Ответ 1
http://en.wikipedia.org/wiki/Closest_pair_of_points
Задача может быть решена в O (n log n) времени с использованием подхода рекурсивного деления и покорения, например, следующим образом:
- Сортировка точек вдоль координаты x
- Разделите множество точек на два подмножества равного размера вертикальной линией x = xmid
- Решите проблему рекурсивно в левом и правом подмножествах. Это даст минимальные расстояния слева и справа на стороне dLmin и dRmin соответственно.
- Найдите минимальное расстояние dLRmin среди пары точек, в которых одна точка лежит слева от разделительной вертикали, а вторая точка лежит вправо.
- Окончательный ответ - это минимум из dLmin, dRmin и dLRmin.
Ответ 2
Я не могу сразу думать о более быстрой альтернативе, чем техника грубой силы (хотя должно быть много), но любой алгоритм, который вы выберете, не вычисляет расстояние между каждой точкой. Если вам нужно сравнить расстояния, просто сравните квадраты расстояний, чтобы избежать дорогого и полностью избыточного квадратного корня.
Ответ 3
Одной из возможностей было бы сортировать точки по их координатам X (или Y - не имеет значения, что, просто быть последовательным). Затем вы можете использовать это, чтобы исключить сравнения со многими другими точками. Когда вы смотрите на расстояние между точкой [i] и точкой [j], если только расстояние X больше текущего кратчайшего расстояния, тогда точка [j + 1]... точка [N] может быть устранена как (предполагая i<j - if j<i, тогда он удаляет точку [0]... point [i]).
Если ваши очки начинаются как полярные координаты, вы можете использовать одну и ту же вещь - сортировать по расстоянию от начала координат, а если разница в расстоянии от источника больше текущего кратчайшего расстояния, вы можете устранить этой точки и всех остальных, которые находятся дальше (или ближе) к источнику, чем тот, который вы сейчас рассматриваете.
Ответ 4
http://blogs.mathworks.com/videos/2008/06/02/matlab-puzzler-finding-the-two-closest-points/
У этого есть целый большой набор различных решений. Непонятно, как много способов найти один и тот же ответ.
Ответ 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;
}
Ответ 6
Вы можете извлечь ближайшую пару в линейном времени из триангуляции Delaunay и, наоборот, из диаграмма Вороного.
Ответ 7
Существует относительно простой алгоритм развертки строк, который может найти ближайшую пару точек в O (nlogn) времени. Это статья содержит краткое объяснение.
Ответ 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.
Если я не ошибаюсь, учитывая коммутативность расстояния, вам не нужно выполнять другие сравнения. В python может показаться что-то
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))
Если более двух точек может иметь одинаковое минимальное расстояние, и вы ищете сегменты, вам нужно снова изменить предлагаемый код, а результатом будет список точек, расстояние которых минимально (или пару точек). Надеюсь, это поможет!