Wie kann man die von-Neumann-Nachbarschaft nutzen, um Indizes im 3D-Raum zu erstellen?

Question

Gegeben ein Index (x,y) im zweidimensionalen Raum (Gitter) kann ich die Nachbarindizes über die von-Neumann-Nachbarschaft ableiten:

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

Wie kann ich dieses Konzept am besten auf den dreidimensionalen Raum ausweiten (mit minimaler Laufzeitkomplexität)? um die Nachbarindizes von (x,y,z) unter Verwendung der von-Neumann-Nachbarschaft abzuleiten?

Kann mir jemand mit etwas Pseudo-/C-Code helfen, um dies zu veranschaulichen?

Answer 1

Wenn es sich um die 6 unmittelbaren Nachbarn handelt, ist es am effizientesten, die Daten zu kodieren:

int neighbour_offsets[3][6] = {
  {1, 0, 0},
  {0, 1, 0},
  {0, 0, 1},
  {-1, 0, 0},
  {0, -1, 0},
  {0, 0, -1},
};

Für die Nachbarn von Rang <= r für feste Dimensionen verschachtelt for Schleifen werden funktionieren:

for (x = -r; x <= r; ++x) {
    r_x = r - abs(x);
    for (y = -r_x; y <= r_x; ++y) {
        r_y = r_x - abs(y);
        for (z = -r_y; z <= r_y; ++z) {
            printf("%d, %d, %d\n", x, y, z);
        }
    }
}

Wenn Sie die Nachbarn auf Abstand halten wollen d == r statt d <= r verwenden z := {-r_y, r_y} .

Für beliebige niedrige Dimensionen wird die Rekursion funktionieren (und einigermaßen klar sein); für hohe Dimensionen beginnen Sie am besten mit einer rekursiven Lösung und wandeln sie in eine Schleife um. In hohen Dimensionen (D >> r) wird der Offset in den meisten Dimensionen ohnehin gleich Null sein.

Answer 2

Das scheint ein bisschen einfach zu sein, vielleicht habe ich Ihre Frage falsch verstanden, aber für beliebige r in drei Dimensionen, in C, würde das Durchlaufen der benachbarten Zellen und deren Verarbeitung oder das Speichern der Indizes etwa so aussehen:

for ( i = -r ; i <= r ; i++ )
    for ( j = -r ; j <= r ; j++ )
        for ( k = -r ; k <= r ; k++ )
            if ( abs(i) + abs(j) + abs(k) <= r ) {
                do whatever in the cell (x+i,y+j,z+k).
                }

Dies ist zwar nicht der effizienteste Weg, aber wahrscheinlich der einfachste.

Answer 3

Wenn Sie nach dem Index eines bestimmten Punktes suchen, ist die Antwort einfach:

sei D die Manhattan-Distanz von 2 Punkten im 3D-Raum:

  D = abs(x1-x2) + abs (y1-y2) + abs (z1 - z2)

und das wäre dann Ihr Index.

Wenn Sie versuchen, das 3D-Oktaeder der von-Neumann-Nachbarschaft zu bauen, dann ist der einfachste Weg, die Rekursion zu verwenden.

In der Tat ist es leicht zu beweisen, dass, wenn ein Punkt X ist im R Bereich von Y y Y ist im K Bereich von Z dann X ist mindestens in der K+R Bereich von Z (Gehe von X nach Y in R Schritten und dann von Y nach Z in K weiteren Schritten).

Diese Lösung benötigt O(n) Zeit, wobei n die genaue Anzahl der Punkte in der Nachbarschaft ist. Sie kann leicht optimiert werden, um Redundanz zu vermeiden.

Ein Beispiel für einen Algorithmus, der eine ähnliche Technik verwendet, ist der Dijkstra-Algorithmus. Obwohl sein Hauptzweck die Pfadsuche ist, besteht sein Prinzip darin, alle Nachbarn des Bereichs 1, dann 2 und so weiter zu erkunden (bei ungewichteten Graphen).