Zu finden in der Nähe von Nachbarn

Ich brauche, um herauszufinden, "in der Nähe von" Nachbarn unter einem Satz von Punkten.

Gibt es 10 Punkte in der Abbildung oben. Rote Linien sind die Kanten der Delaunay-Triangulationdie schwarzen Sterne markieren Sie die Mitte der Linien der Kanten, die blauen Linien sind die Voronoi-tesselation. Punkt 1 hat drei "in der Nähe von" Nachbarn, also 4, 6, und 7, aber nicht 2 und 3, die fast in einer Linie mit dem Rand 1-7, aber viel weiter Weg.

Was ist ein guter Weg, um zu identifizieren, die in der Nähe Nachbarn (oder "gute" Kanten)? Blick auf die Abbildung, es scheint mir, dass entweder die Auswahl der Kanten, deren Mitte der Punkt auf der Kreuzung mit der Voronoi-Linien, oder wenn man bedenkt, wie "nahe" Nachbarn jene, die mit Berührung Voronoi-Zellen könnte eine gute Lösung sein (die Einstufung von 3-5 kann in beide Richtungen gehen). Gibt es eine effiziente Art und Weise der Umsetzung der beiden Lösungen in Matlab (ich wäre froh, um einen guten Allgemeinen Algorithmus, die kann ich dann übersetzen zu Matlab, btw)?

InformationsquelleAutor der Frage Jonas | 2011-02-10

8

Können Sie die Umsetzung Ihrer ersten Idee, der Auswahl der Kanten, deren mid-Punkten an der Kreuzung mit der Voronoi-Linien, die durch die Nutzung der DelaunayTri Klasse und seine Kanten und nearestNeighbor Methoden. Hier ist ein Beispiel mit 10 zufällige Paare von x und y Werte:
```
x = rand(10,1);                     %# Random x data
y = rand(10,1);                     %# Random y data
dt = DelaunayTri(x,y);              %# Compute the Delaunay triangulation
edgeIndex = edges(dt);              %# Triangulation edge indices
midpts = [mean(x(edgeIndex),2) ...  %# Triangulation edge midpoints
          mean(y(edgeIndex),2)];
nearIndex = nearestNeighbor(dt,midpts);  %# Find the vertex nearest the midpoints
keepIndex = (nearIndex == edgeIndex(:,1)) | ...  %# Find the edges where the
            (nearIndex == edgeIndex(:,2));       %#   midpoint is not closer to
                                                 %#   another vertex than it is
                                                 %#   to one of its end vertices
edgeIndex = edgeIndex(keepIndex,:);      %# The "good" edges
```
Und jetzt edgeIndex ist ein N-von-2-matrix, wo jede Zeile enthält die Indizes in x und y für eine Kante, die definiert, "in der Nähe" - Verbindung. Der folgende plot zeigt die Delaunay-triangulation (rote Linien) Voronoi Diagramm (Blaue Linien), die Mittelpunkte der Kanten der triangulation (schwarze Sternchen), und das "gute" Kanten, die bleiben in edgeIndex (Dicke rote Linien):
```
triplot(dt,'r');  %# Plot the Delaunay triangulation
hold on;          %# Add to the plot
plot(x(edgeIndex).',y(edgeIndex).','r-','LineWidth',3);  %# Plot the "good" edges
voronoi(dt,'b');  %# Plot the Voronoi diagram
plot(midpts(:,1),midpts(:,2),'k*');  %# Plot the triangulation edge midpoints
```
Wie es funktioniert...

Das Voronoi-Diagramm besteht aus einer Reihe von Voronoi-Polygonen, oder Zellen. In dem obigen Bild, jede Zelle stellt die region rund um einen bestimmten triangulation vertex umschließt alle Punkte im Raum, die näher an dieser Ecke als alle anderen vertex. Als Ergebnis dieser, wenn du 2 vertices, die nicht in der Nähe zu jedem anderen Knoten (wie die Eckpunkte 6 und 8 im Bild) dann wird der Mittelpunkt der Verbindungslinie zwischen diesen Eckpunkten fällt auf die Trennlinie zwischen den Voronoi-Zellen für die Eckpunkte.

Jedoch, wenn es einen Dritten Eckpunkt, der in der Nähe der Verbindungslinie zwischen 2 vertices dann ist die Voronoi-Zelle für die Dritte vertex erweitern kann zwischen 2 Eckpunkten, über die Linie verbindenden und umschließenden, dass die Zeilen Mittelpunkt. Dieser Dritte Eckpunkt kann daher als "näher" Nachbarn aus dem 2 Eckpunkte gegeben als die 2 vertices miteinander. In Ihrem Bild, die Voronoi-Zelle für Scheitelpunkt 7 erstreckt sich in der region zwischen den Eckpunkten 1 und 2 (1 und 3), also vertex-7 als eine nähere Nachbar-Eckpunkt 1 Eckpunkt 2 (oder 3) ist.

In manchen Fällen kann dieser Algorithmus möglicherweise nicht betrachten Sie zwei vertices als "in der Nähe" Nachbarn, obwohl Ihre Voronoi-Zellen berühren. Eckpunkte 3 und 5 in deinem Bild sind ein Beispiel dafür, wo die vertex 2 ist als eine nähere Nachbar-Eckpunkte 3 oder 5 als Eckpunkte 3 oder 5 auf einander.

InformationsquelleAutor der Antwort gnovice
1

Ich würde Zustimmen, dass die gemeinsame Zelle von Kanten ist ein guter Nachbar Kriterium (in diesem Beispiel). Wenn Sie wurden mit einer mesh-orientierte Datenstruktur (wie etwas aus der Gts), dann ist die Identifizierung der gemeinsamen Kanten wäre trivial.

Matlab, auf der anderen Seite, macht diese eher "interessant". Vorausgesetzt, die voronoi-Zellen sind, werden als patches, könnten Sie versuchen, den Erhalt der "Gesichter" patch-Eigenschaft (siehe diese Referenz). Das sollte zurückkehren, so etwas wie eine Nachbarschaft-matrix, die identifiziert verbundenen vertices. Aus diesem (und ein wenig Magie), Sie sollten in der Lage sein, um zu bestimmen, gemeinsame Ecken, und dann ableiten der gemeinsamen Kanten. In meiner Erfahrung, diese Art der "Suche" - problem eignet sich nicht für die Matlab - wenn möglich, empfehle ich, den übergang zu einem system besser geeignet, um Abfragen der Netz-Konnektivität.

InformationsquelleAutor der Antwort Throwback1986
0

Andere Möglichkeit, einfacher als das erstellen von Triangulationen oder von voronoi-Diagrammen, ist mit einem Nachbarschaft matrix.

Ersten Platz alle Ihre Punkte in einem 2D-quadratische matrix. Dann führen Sie einen vollständigen oder teilweisen räumlichen Sortieren, also die Punkte wurde bestellt in der matrix.

Punkte mit kleinen Y bewegen konnte, um die oberen Reihen der matrix, und ebenso, Punkte mit großen Y gehen würde, um die unteren Zeilen. Das gleiche passiert mit Punkten, die mit kleinen X-Koordinaten, das sollte sich nach den Spalten auf der linken Seite. Und symmetrisch, Punkte mit großen X-Wert wird auf der rechten Spalten.

Nachdem der räumlichen Art (es gibt viele Wege, dies zu erreichen, sowohl durch serielle oder parallele algorithmen) können Sie nachschlagen die nächsten Punkte von einem gegebenen Punkt P, besuchen Sie einfach die angrenzenden Zellen, in denen der Punkt P tatsächlich gespeichert in der Nachbarschaft-matrix.

Lesen Sie mehr details für diese Idee in der folgenden Papier (finden Sie PDF-Kopien der it-online): Supermassive Crowd-Simulation auf der GPU, basierend auf Emergenten Verhalten.

Sortierung Schritt bietet Sie interessante Möglichkeiten. Sie können nur das gerade-ungerade-transposition sort in diesem Papier beschrieben, das ist sehr einfach zu implementieren (auch in CUDA). Wenn Sie nur einen pass, wird es geben Sie eine teilweise Sortieren, das kann schon nützlich, wenn die matrix ist in der Nähe-sortiert. Das ist, wenn Sie Ihre Punkte bewegen sich langsam, es wird Sie sparen eine Menge Rechenleistung.

Wenn Sie müssen eine vollständige Art, die Sie ausführen können eine solche auch-merkwürdig Umsetzung Durchlaufen Sie mehrere Male (wie beschrieben in der folgenden Wikipedia-Seite):

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

InformationsquelleAutor der Antwort mgmalheiros

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

Wie es funktioniert...