Algoritmo de distancia más corta entre puntos

Question

Dado un conjunto de puntos en un plano, encuentre el segmento de recta más corto formado por dos de estos puntos.

¿Cómo puedo hacer eso?La forma trivial es obviamente calcular cada distancia, pero necesito otro algoritmo para comparar.

Answer 1

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

El problema se puede resolver en tiempo O (n log n) utilizando el enfoque recursivo de dividir y conquistar, por ejemplo, de la siguiente manera:

• Ordenar puntos a lo largo de la coordenada x
• Divida el conjunto de puntos en dos subconjuntos del mismo tamaño por una línea vertical x = xmid
• Resuelve el problema de forma recursiva en los subconjuntos izquierdo y derecho. Esto le dará a las distancias mínimas del lado izquierdo y del lado derecho dLmin y dRmin respectivamente.
• Encuentre la distancia mínima dLRmin entre el par de puntos en los que un punto se encuentra a la izquierda de la vertical divisoria y el segundo punto se encuentra a la derecha.
• La respuesta final es el mínimo entre dLmin, dRmin y dLRmin.

Answer 2

No puedo pensar de inmediato en una alternativa más rápida que la técnica de fuerza bruta (aunque debe haber muchas), pero cualquiera que sea el algoritmo que elija no calculará la distancia entre cada punto. Si necesita comparar distancias, simplemente compare los cuadrados de las distancias para evitar la raíz cuadrada costosa y completamente redundante.

Answer 3

Una posibilidad sería ordenar los puntos por sus coordenadas X (o la Y, en realidad no importa cuál, solo sea consistente). Luego puede usar eso para eliminar las comparaciones con muchos de los otros puntos. Cuando observa la distancia entre el punto [i] y el punto [j], si la distancia X sola es mayor que la distancia más corta actual, entonces el punto [j + 1] ... el punto [N] puede eliminarse como bien (suponiendo i<j - si j<i, entonces es el punto [0] ... el punto [i] que se eliminan).

Si sus puntos comienzan como coordenadas polares, puede usar una variación de la misma cosa: ordenar por distancia desde el origen, y si la diferencia en la distancia desde el origen es mayor que la distancia más corta actual, puede eliminar ese punto, y todos los demás que están más lejos (o más cerca) del origen que el que estás considerando actualmente.

Answer 4

Puede extraer el par más cercano en tiempo lineal de la triangulación de Delaunay y viceversa desde < a href = "http://en.wikipedia.org/wiki/Voronoi_diagram" rel = "nofollow noreferrer"> Diagrama de Voronoi .

Answer 5

Hay un algoritmo estándar para este problema, aquí puede encontrarlo: http://www.cs.mcgill.ca/~cs251/ClosestPair/ ClosestPairPS.html

Y aquí está mi implementación de este algo, lo siento sin comentarios:

    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

De su pregunta no queda claro si está buscando la distancia del segmento o el segmento en sí.Suponiendo que estás buscando la distancia (el segmento es entonces una simple modificación, una vez que sabes cuáles son los dos puntos cuya distancia es mínima), dados 5 puntos, numerados del 1 al 5, necesitas

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.

Si no me equivoco, dada la conmutatividad de la distancia no es necesario realizar otras comparaciones.En Python, puede sonar como algo

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

Eso se puede probar con algo como el siguiente código:

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))

Si más de dos puntos pueden tener la misma distancia mínima y está buscando los segmentos, deberá modificar nuevamente el código propuesto y el resultado será la lista de puntos cuya distancia es mínima (o un par de puntos).¡Espero eso ayude!