Suche nächstgelegenen Punkt in einer effizienten Art und Weise

Habe ich einen Punkt in der 2d Ebene zum Beispiel (x0,y0) und eine Menge von n Punkten (x1,y1)...(xn,yn) und ich möchte nächstgelegene Punkt (x0,y0) in einer Weise, die besser ist, als zu versuchen, alle Punkte. Alle Lösungen?

Sollte ich auch sagen, dass meine Punkte sind auf diese Art sortiert:

bool less(point a,point b){
  if(a.x!=b.x)
     return a.x<b.x;
  else
     return a.y<b.y;
 }
  • Ist x0 und y0 das erste element in das sortierte Liste der Punkte?
  • Nein. Es ist komplett aus der Liste 😀
  • Ist der Punkt willkürlich? Ändert es? Das heißt, wird Sie später finden wollen, den nächsten Punkt zu einem anderen Punkt?
  • Ich kann Abfragen möchten für viele verschiedene Punkte
InformationsquelleAutor | 2010-12-22
  1. 9

    Verwendung eines quad-trees für 2D
    http://en.wikipedia.org/wiki/Quadtree

    InformationsquelleAutor VGE
  2. 8

    Voronoi-Diagramm ist speziell für die Suche nach nächsten Punkt sehr schnell. Obwohl es durchaus ein Schmerz zu implementieren, finden Sie möglicherweise einige vorhandene Bibliothek/Umsetzung.

    Es ist auch eine option, um immer wieder die Aufteilung der Ebene in Quadrate, also eine Art Baum, wo jeder nicht-Blatt-Knoten hat 4 Kinder (oben rechts, Quadrat, unten-rechts, Quadrat, etc.). Dann, vier Plätze, die Sie finden, die Ihren Punkt an und fahren Sie mit es rekursiv. Oft ergibt sich der Punkt nahe genug, so können Sie beseitigen die Notwendigkeit zu prüfen anderen Plätzen.

    Aber es ist einfach, erstellen Sie ein "Gegenbeispiel" für diese Strategie, welche wird Ergebnis in der linearen Zeit.

    Aber es gibt nicht viel Sie tun können, mit Ihrem sortierte array den Prozess zu beschleunigen. Sie benötigen eine spezielle Datenstruktur.

    Bearbeiten

    Die zweite Struktur ist genannt Quadtree, Dank VGE für die Bereitstellung der Namen.

    • Es mag zwar overkill, verbringen Sie O(n log n) Operationen den Aufbau Ihrer Voronoi-Diagramm, sondern danach, jeder nächste Nachbar kann nachgeschlagen werden in O(log n) Zeit. Vergleichen Sie dies mit O(n), die für naive iteration. Auch, ich empfehlen Sie mit CGAL zur Berechnung des Voronoi-Diagramms (durch Delaunay-triangulation). CGAL ist kompliziert, aber der Delaunay-Algorithmus ist sehr empfindlich auf roundoff Fehler, und Sie sollten nicht es selbst implementieren: Sie müssen die (unter anderem) anpassungsfähiger precision floating point-zahlen.
    • Nur das problem ist die Implementierung der Datenstruktur :-). Auch, CGAL ist eine sehr teure Bibliothek, es sei denn Sie sind open-sourcing von Ihren eigenen code.
    • Ich wusste nicht, cgal wurde dual lizensiert. Die Datenstruktur ist in der Tat ganz natürlich. Das eigentliche problem liegt in der unstable-test "in einem umschriebenen Kreises eines Dreiecks": wenn die Dreieck-Punkte sind fast ausgerichtet, die Berechnung ist sehr unaccurate und Erträge die falsche triangulation.
    • Ja ich bin sehr gut auf dieses problem aufmerksam :-). Ich habe Monate damit verbracht zu arbeiten, auf eine triangulation Algorithmus versucht, es zu beheben. Natürlich wusste ich nicht, gelingen, und der schlechte code ist noch von unglücklichen Kunden...
    • Ich fürchte, Sie haben zu verwenden, adaptive floating-point-Berechnungen. Es gibt eine Menge von Möglichkeiten, dies zu tun, habe ich vielleicht einige Papiere praktisch, wenn Sie interessiert sind.
    InformationsquelleAutor Nikita Rybak
  3. 6

    Zur effizienten nächste-Nachbar-Suche, die Sie brauchen, um eine räumliche Partitionierung, zum Beispiel eine k - d-Baum.

    InformationsquelleAutor Gareth Rees
  4. 2

    Wenn Sie nicht verwenden, jede Art von Baum-Datenstruktur zu helfen, begrenzen den Bereich der Werte, die Sie haben, zu Abfrage -, Sie gehen zu müssen, überprüfen, um jeden Punkt in Ihrem Bereich des möglichen "Nachbarn". Eine Möglichkeit zur Begrenzung der Vergleiche wäre zu prüfen, dem Quadrat der Entfernung von Ihr bestimmten Zeitpunkt die für den kleinsten Wert:

    Point myPoint = {x, y};
std::vector<Point> otherPoints; //given list of points to check

struct PointDistance
{
    Point pt;
    float dist;
};

std::vector<PointDistance> squaredDistances(otherPoints.size()); //will be filled in with squared distances

float CalculateDistance(const Point& pt1, const Point& pt2)
{
    float deltaX = pt1.x - pt2.x;
    float deltaY = pt1.y - pt2.y;
    return (deltaX * deltaX) + (deltaY * deltaY);
}

//should be changed to use an algorithm, but for clarity done as a loop here
for (int i = 0; i < otherPoints.size(); ++i)
{
    PointDistance pd;
    pd.pt = otherPoints[i];
    pd.dist = CalculateDistance(myPoint, pd.pt);
    squaredDistances.push_back(pd);
}

bool DistanceLess(const PointDistance& lhs, const PointDistance& rhs)
{
    return lhs.dist < rhs.dist;
}

std::sort(squaredDistances.begin(), squaredDistances.end(), DistanceLess);

//squaredDistances[0].pt will be your closest point.
    • std::min_element() liefert die Antwort mit weniger Komplexität (max(N-1,0) - Vergleiche) als std::sort() (O(N·log(N))). Mit Ausnahme der Fehlerbehandlung auf, so ergibt sich der nächste Punkt: std::min_element(...)->pt.
    • Ja, std::min_element ist eine gute alternative zur Sortierung der quadrierten Distanzen für die nur das minimale element.
    InformationsquelleAutor Zac Howland
  5. 0

    Wenn Sie die Menge von N Punkten dann statt nur schob Sie in eine Reihe, Sie können die hash-map, basierend auf der linearen Distanz von dem Punkt, unter Berücksichtigung . Also Punkte mit gleichen linearen Abstand in der gleichen Eimer. Dann Holen die Punkt(E) auf der Grundlage der Entfernung wird eine Konstante Zeit Betrieb.

    • Ich kann das nicht tun. da mein Bezugspunkt kann sich ändern.
    InformationsquelleAutor yasouser
  6. 0

    Eine besonders schöne Lösung ist ANN: A Library for Approximate Nearest Neighbor-Suche. ich habe es für Punkt-zu-Standort in Triangulationen. Sie initialisiert eine Datenstruktur mit dem Punkte, in meinem Fall habe ich die Mittelpunkte von meiner Dreiecke. Dann können Sie den pass in einem anderen Punkt und wieder Liste mit den ungefähren nächsten Nachbarn Punkte. Auch die Anzahl der Punkte, die zurückgegeben wird, ist wählbar als parameter. Trotzdem ANN war eine große Bibliothek, für meine Zwecke, dann empfehle ich Ihnen, check it out.

    Glück!

    InformationsquelleAutor Daniel Lidström
Schreibe einen Kommentar