algorithm - triangulacion - puntos mas cercanos divide y venceras

Distancia más corta entre los puntos algoritmo

Question

Dado un conjunto de puntos en un plano, encuentre el segmento de línea 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

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

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 estoy equivocado, 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, necesita modificar nuevamente el código propuesto, y la salida será la lista de puntos cuya distancia es mínima (o un par de puntos). ¡Espero eso ayude!

Answer 2

Hay un algoritmo estándar para este problema, aquí lo puede encontrar: 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 3

No puedo pensar inmediatamente en una alternativa más rápida que la técnica de fuerza bruta (aunque debe haber suficiente), pero sea cual sea el algoritmo que elijas , no calcules 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 4

Puede extraer el par más cercano en tiempo lineal a partir de la triangulación de Delaunay y viceversa del diagrama de Voronoi .

Answer 5

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

El problema se puede resolver en el tiempo O (n log n) usando el enfoque recursivo 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 de igual tamaño por una línea vertical x = xmid
• Resuelva el problema recursivamente en los subconjuntos izquierdo y derecho. Esto le dará a las distancias mínimas dLmin y dRmin del lado izquierdo y derecho, respectivamente.
• Encuentre la distancia mínima dLRmin entre el par de puntos en el que un punto se encuentra a la izquierda de la división vertical y el segundo punto a la derecha.
• La respuesta final es el mínimo entre dLmin, dRmin y dLRmin.

Answer 6

Una posibilidad sería clasificar los puntos por sus coordenadas X (o la Y, realmente no importa, que sea consistente). Puede usar eso para eliminar las comparaciones con muchos de los otros puntos. Cuando mira la distancia entre el punto [i] y el punto [j], si la distancia X sola es mayor que su distancia más corta actual, entonces el punto [j + 1] ... el punto [N] puede eliminarse como bien (asumiendo que 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 la distancia desde el origen, y si la diferencia en la distancia desde el origen es mayor que su distancia más corta actual, puede eliminar ese punto, y todos los demás que están más lejos (o más cerca de) el origen que el que está considerando actualmente.