La distanza più breve tra i punti dell'algoritmo

Question

Dato un insieme di punti su un piano, trova il segmento di linea più corto formato da uno qualsiasi di questi due punti.

Come posso farlo? Il modo banale è ovviamente calcolare ogni distanza, ma ho bisogno di un altro algoritmo per confrontare.

Answer 1

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

Il problema può essere risolto in O (n log n) tempo usando l'approccio ricorsivo di divisione e conquista, ad esempio, come segue:

• Ordina i punti lungo la coordinata x
• Dividi l'insieme di punti in due sottoinsiemi di dimensioni uguali per una linea verticale x = xmid
• Risolve il problema in modo ricorsivo nei sottoinsiemi sinistro e destro. Ciò fornirà le distanze minime dLmin e dRmin rispettivamente sul lato sinistro e sul lato destro.
• Trova la distanza minima dLRmin tra la coppia di punti in cui un punto si trova a sinistra della verticale di divisione e il secondo punto si trova a destra.
• La risposta finale è il minimo tra dLmin, dRmin e dLRmin.

Answer 2

Non riesco immediatamente a pensare a un'alternativa più rapida della tecnica della forza bruta (anche se ci deve essere molto) ma qualunque algoritmo che scegli non calcola la distanza tra ogni punto. Se devi confrontare le distanze, confronta i quadrati delle distanze per evitare la radice quadrata costosa e interamente ridondante.

Answer 3

Una possibilità sarebbe quella di ordinare i punti in base alle loro coordinate X (o Y - non importa davvero quale, solo essere coerenti). Puoi quindi usarlo per eliminare i confronti con molti altri punti. Quando guardi la distanza tra il punto [i] e il punto [j], se la sola distanza X è maggiore della tua distanza più breve attuale, il punto [j + 1] ... punto [N] può essere eliminato come bene (supponendo i<j - se j<i, allora il punto [0] ... punto [i] che viene eliminato).

Se i tuoi punti iniziano come coordinate polari, puoi utilizzare una variazione della stessa cosa: ordina per distanza dall'origine e se la differenza di distanza dall'origine è maggiore della tua distanza più breve corrente, puoi eliminare quel punto e tutti gli altri che sono più lontani (o più vicini) dall'origine rispetto a quello che stai attualmente considerando.

Answer 4

Puoi estrarre la coppia più vicina in tempo lineare dalla triangolazione Delaunay e viceversa da < a href = "http://en.wikipedia.org/wiki/Voronoi_diagram" rel = "nofollow noreferrer"> diagramma di Voronoi .

Answer 5

Esiste un algoritmo standard per questo problema, qui puoi trovarlo: http://www.cs.mcgill.ca/~cs251/ClosestPair/ ClosestPairPS.html

Ed ecco la mia implementazione di questo algo, scusate se non ci sono commenti:

    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

Dalla tua domanda non è chiaro se stai cercando la distanza del segmento o il segmento stesso. Supponendo che tu stia cercando la distanza (il segmento in una semplice modifica, una volta che sai quali sono i due punti la cui distanza è minima), dati 5 punti, numerati da 1 a 5, devi

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.

Se non sbaglio, data la commutatività della distanza non è necessario eseguire altri confronti. In Python, può sembrare qualcosa

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

Che può essere testato con qualcosa come il seguente codice:

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

Se più di due punti possono avere la stessa distanza minima e stai cercando i segmenti, devi nuovamente modificare il codice proposto e l'output sarà l'elenco di punti la cui distanza è minima (o coppia di punti ). Spero che sia d'aiuto!