Algorithmus zum Finden des nächsten Objekts auf dem 2D-Gitter

Question

Angenommen, Sie haben ein 2D-Gitter mit jeder Stelle im Gitter mit x Anzahl der Objekte (mit x> = 0). Ich habe Probleme, an einen sauberen Algorithmus zu denken, so dass, wenn ein Benutzer eine Koordinate spezifiziert, der Algorithmus die nächstliegende Koordinate (einschließlich der spezifizierten) mit einem Objekt darauf findet.

Der Einfachheit halber nehmen wir an, dass, wenn 2 Koordinaten die gleiche Entfernung sind, die erste zurückgegeben wird (oder wenn Ihr Algorithmus nicht so funktioniert, dann spielt der letzte keine Rolle).

Bearbeiten: Eine Koordinate, die 1 entfernt ist, muss entweder 1 oben, unten, links oder rechts sein. Koordinaten, die diagonal weg sind, sind 2.

Als eine Randnotiz, was ist eine große, kostenlose, Online-Referenz für Algorithmen?

Answer 1

Udate

Mit neuen Informationen:

, dass ein diagonal Unter der Annahme Koordinate 2 entfernt

Dieser Algorithmus funktionieren würde. Der Algorithmus sucht spiralförmig nach außen, um jeden Punkt in jedem von innen begonnenen "Ring" zu testen.

Beachten Sie, dass es Situationen außerhalb der Grenzen nicht behandelt. Sie sollten dies also an Ihre Bedürfnisse anpassen.

int xs, ys; // Start coordinates 

// Check point (xs, ys) 

for (int d = 1; d<maxDistance; d++) 
{ 
    for (int i = 0; i < d + 1; i++) 
    { 
     int x1 = xs - d + i; 
     int y1 = ys - i; 

     // Check point (x1, y1) 

     int x2 = xs + d - i; 
     int y2 = ys + i; 

     // Check point (x2, y2) 
    } 


    for (int i = 1; i < d; i++) 
    { 
     int x1 = xs - i; 
     int y1 = ys + d - i; 

     // Check point (x1, y1) 

     int x2 = xs + d - i; 
     int y2 = ys - i; 

     // Check point (x2, y2) 
    } 
} 

Alte Version

Unter der Annahme, dass der Abstand zwischen (0, 0) und (1, 0) in der 2D-Gitter ist das gleiche wie (0, 0) und (1, 1) . Dieser Algorithmus würde funktionieren. Der Algorithmus sucht spiralförmig nach außen, um jeden Punkt in jedem von innen begonnenen "Ring" zu testen.

Beachten Sie, dass es Situationen außerhalb der Grenzen nicht behandelt. Sie sollten dies also an Ihre Bedürfnisse anpassen.

int xs, ys; // Start coordinates 

if (CheckPoint(xs, ys) == true) 
{ 
    return (xs, ys); 
} 

for (int d = 0; d<maxDistance; d++) 
{ 
    for (int x = xs-d; x < xs+d+1; x++) 
    { 
     // Point to check: (x, ys - d) and (x, ys + d) 
     if (CheckPoint(x, ys - d) == true) 
     { 
      return (x, ys - d); 
     } 

     if (CheckPoint(x, ys + d) == true) 
     { 
      return (x, ys - d); 
     } 
    } 

    for (int y = ys-d+1; y < ys+d; y++) 
    { 
     // Point to check = (xs - d, y) and (xs + d, y) 
     if (CheckPoint(x, ys - d) == true) 
     { 
      return (xs - d, y); 
     } 

     if (CheckPoint(x, ys + d) == true) 
     { 
      return (xs - d, y); 
     } 
    } 
} 

Answer 2

Wenn Sie eine Liste von Objekten haben

Wenn Sie die Objekte in einer Liste alle Positionen aller hatte, dies wäre viel einfacher sein, wie man es nicht alle leeren Felder suchen müssen und könnte 2D distance calculations durchführen, um den nächsten zu bestimmen. Schleife durch die Liste von Objekten und den Abstand wie folgt berechnen:

Define your two points. Point 1 at (x1, y1) and Point 2 at (x2, y2). 

    xd = x2-x1 
    yd = y2-y1 
    Distance = SquareRoot(xd*xd + yd*yd) 

Dann einfach auf einen Blick mit der kürzesten Entfernung.

Wenn Sie nur ein 2D-Array haben

Wenn jedoch das Problem, wie ein 2D-Array davon ausgegangen, beschrieben, bei dem die Positionen der Objekte, ohne zunächst die Suche nach alle von ihnen können nicht Sie gehen zu müssen, dann aufgeführt werden, eine Spiralschleife machen.

Suchen nach 'Spiral Search Method' kommt mit ein paar interessanten Links. Here is some code that does a spiral loop um ein Array, jedoch funktioniert dies nicht von einem beliebigen Punkt und Spirale nach außen, aber sollte Ihnen einige gute Ideen geben, wie Sie erreichen, was Sie wollen.

Hier ist ein similar question über das Füllen von Werten in der Spiralreihenfolge in einem 2D-Array.

Wie auch immer, hier ist, wie ich das Problem angehen würde:

gegebenen Punkt P, erstellen Sie ein Vektorpaar, das einen Bereich um P angibt. So

wenn P = 4,4 Dann würde dein Vektor Paar seine 3,3|5,5

Schleifen jeden Wert in den Grenzen.

for x = 3 to 5 
    for y = 3 to 5 
     check(x,y) 
    next 
next 

Wenn ein Wert gefunden wird, beenden Sie. Wenn nicht, erhöhen Sie die Grenzen erneut um eins. In diesem Fall würden wir zu 2,2 gehen. 6,6

Wenn Sie die Werte überprüfen, stellen Sie sicher, dass wir keine negativen Indizes angegeben haben und dass die Größe des Arrays nicht überschritten wurde .

Auch wenn Sie die Schranken n-mal erweitern, müssen Sie nur die äußeren Randwerte schleifen, Sie müssen die inneren Werte nicht erneut prüfen.

Welche Methode ist schneller?

Es hängt alles von:

• Die Dichte Ihrer Array
• Verteilungstechnik
• Anzahl der Objekte

Dichte von Array

Wenn Sie ein 500x500 Array mit 2 Ob jekte in ihm, dann die Liste Looping wird immer eine Spirale

Verteilungstechnik

Wenn es Muster der Verteilung (dh die Objekte neigen dazu, clustern umeinander) dann eine Spirale durchführen kann schneller Outperform tun.

Anzahl der Objekte

Eine Spirale wird wahrscheinlich schneller durchführen, wenn es eine Million Objekte sind, wie die Liste Technik, die Sie alle Entfernungen, zu überprüfen und berechnen erfordert.

Sie sollten in der Lage sein, die schnellste Lösung zu berechnen, indem Sie die Wahrscheinlichkeit eines Platzes berechnen, verglichen mit der Tatsache, dass die Listenlösung jedes Objekt jedes Mal überprüfen muss.

Mit der List-Technik können Sie jedoch einige intelligente Sortierung durchführen, um die Leistung zu verbessern. Es lohnt sich, es genauer zu betrachten.

Answer 3

Wenn Ihre Objekte dicht sind, ist die Suche nach den nächstgelegenen Punkten wahrscheinlich die beste Methode, um das nächstgelegene Objekt zu finden, das sich aus der Mitte heraus erstreckt. Wenn Ihre Objekte spärlich sind, dann ist eine oder ähnliche Datenstruktur (R-Baum, etc.) wahrscheinlich besser. Hier ist ein writeup mit Beispielen.

Ich weiß nicht, eine gute Online-Algorithmus Referenz, aber ich kann sagen, dass, wenn Sie mehr als die gelegentliche Codezeile schreiben, sparen Ihre Pfennige zu kaufen CLRS wird das Geld wert sein. Es gibt Vorträge basierend auf diesem Buch online, die sorgfältig von Peteris Krumins kommentiert wurden, aber sie decken nur einen Teil des Buches ab. Dies ist eines der wenigen Bücher, die Sie besitzen müssen.

Answer 4

Die folgende einfache Lösung geht davon aus, dass Sie zusätzliche Informationen pro Rasterzelle Speicherung leisten können, und dass die Zeit, Kosten an das Netz neue Objekte der Zugabe darf relativ hoch sein.

Die Idee ist, dass jede Zelle einen Verweis auf die am nächsten besetzten Zelle hält, also O (1) Abfragezeit ermöglicht. Wenn ein Objekt zur Position (i, j) hinzugefügt wird, führen Sie einen Scan der umgebenden Zellen durch, wobei Ringe mit zunehmender Größe abgedeckt werden. Analysieren Sie für jede Zelle, die gerade gescannt wird, die aktuellste Referenz für die besetzte Zelle, und ersetzen Sie sie bei Bedarf. Der Prozess endet, wenn der letzte gescannte Ring überhaupt nicht geändert wird. Im schlimmsten Fall scannt der Prozess alle Gitterzellen, aber schließlich wird es besser, wenn das Gitter dicht genug wird.

Diese Lösung ist einfach zu implementieren, kann einen erheblichen Raum Overhead (je nachdem, wie das Raster im Speicher organisiert ist), sondern sorgt für eine optimale Abfragezeit.