Kürzester Abstand zwischen den Punkten Algorithmus
https://stackoverflow.com/questions/1602164
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
eine Reihe von Punkten auf einer Ebene gegeben, das kürzeste Liniensegment durch zwei diese Punkte gebildet finden.
Wie kann ich das tun? Die triviale Weise ist offensichtlich jede Entfernung zu berechnen, aber ich brauche einen anderen Algorithmus zu vergleichen.
Lösung
http://en.wikipedia.org/wiki/Closest_pair_of_points
Das Problem kann gelöst werden, in O Zeit (n log n) die rekursive Verwendung divide und Herrsche Ansatz, beispielsweise wie folgt:
- Sortieren Punkten entlang der x-Koordinate
- Teilen Sie die Menge von Punkten in zwei gleich große Teilmengen durch eine vertikale Linie x = xmid
- Lösen Sie das Problem rekursiv in der linken und rechten Teilmengen. Dadurch werden die linken und rechten Seite minimale Abstände dLmin und DRMIN geben sind.
- , um ein Minimalabstand dLRmin zwischen dem Paar von Punkten, in denen ein Punkt auf der linken Seite der vertikalen Teilung und dem zweiten Punkt liegt, liegt auf der rechten Seite.
- Die letzte Antwort ist das Minimum unter dLmin, DRMIN und dLRmin.
Andere Tipps
Ich kann nicht sofort denken Sie an eine schnellere Alternative als die Brute-Force-Technik (obwohl es muss viel sein), aber was auch immer Algorithmus Sie wählen nicht , um den Abstand zwischen jedem Punkt zu berechnen. Wenn Sie Abstände vergleichen müssen nur vergleichen Sie die Quadrate der Entfernungen, die teure und vollständig redundante Quadratwurzel zu vermeiden.
Eine Möglichkeit wäre es, die Punkte durch ihre X-Koordinaten zu sortieren (oder die Y - nicht wirklich wichtig, die, nur konsequent sein). Sie können dann, dass Vergleiche der anderen Punkte zu viele beseitigen verwenden. Wenn Sie an dem Abstand zwischen dem Punkt [i] und Punkt [j] suchen, wenn der X allein Abstand größer als die aktuellen kürzeste Entfernung ist, zeigen Sie dann auf [j + 1] ... Punkt [N] als beseitigt werden gut (unter der Annahme i<j - wenn j<i, dann ist es Punkt [0] ... point [i], die eliminiert werden)
Wenn Sie Ihre Punkte als Polarkoordinaten beginnen, können Sie eine Variation von der gleichen Sache verwenden - sortiert nach Entfernung vom Ursprung, und wenn die Differenz in Abstand vom Ursprung ist größer als die aktuelle kürzeste Entfernung, können Sie beseitigen dieser Punkt, und alle anderen, die weiter von (oder näher) die Herkunft als die sind, die Sie gerade betrachten.
Sie können das nächste Paar in linearer Zeit Auszug aus der Delaunay-Triangulation und conversly von < a href = "http://en.wikipedia.org/wiki/Voronoi_diagram" rel = "nofollow noreferrer"> Voronoidiagramm .
Es gibt einen Standard-Algorithmus für dieses Problem ist, hier können Sie es finden: http://www.cs.mcgill.ca/~cs251/ClosestPair/ ClosestPairPS.html
Und hier ist meine Umsetzung dieser algo, sorry es ist ohne Kommentar:
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;
}
Aus Ihrer Frage ist es nicht klar, ob man für die Entfernung des Segments suchen, oder das Segment selbst. Angenommen, Sie sind für die Ferne (das Segment in dann eine einfache Modifikation, wenn Sie wissen, was die beiden Punkte, deren Abstand minimal sind), 5 Punkte gegeben, nummeriert von 1 bis 5, müssen Sie
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.
Wenn ich nicht falsch bin, angesichts der commutativity der Strecke, die Sie nicht brauchen, andere Vergleiche durchzuführen. In Python, klingt wie etwas
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
Das kann mit so etwas wie dem folgenden Code getestet werden:
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))
Wenn mehr als zwei Punkte können die gleichen minimalen Abstand haben, und Sie sind für die Segmente, müssen Sie erneut den vorgeschlagenen Code zu ändern, und die Ausgabe wird die Liste der Punkte, deren Abstand minimal (oder einige Punkte sein ). Hoffe, es hilft!
