Holen Sie sich Ring von Fliesen in Sechseckgitter

Dank dieses Beitrags: Sechseckige Kacheln und Finden ihrer benachbarten Nachbarn kann ich benachbarte Kacheln zu einer bestimmten Kachel sammeln. Aber ich bin ziemlich auf einen Algorithmus fixiert, der mir nur einen "Ring" von Kacheln gibt, der durch einen Versatz angegeben wird. Der in diesem Stapelüberlauf-Beitrag angegebene Algorithmus berücksichtigt nicht genau die Reihenfolge, in der die Kacheln gesammelt werden.

Ich weiß, dass mit jedem Versatz 6 Kacheln hinzugefügt werden.

Mit Versatz 1 erhalten Sie 6 Kacheln (die ersten benachbarten Kacheln).
Offset 2 ergibt 12.
Offset 3 ergibt 18 usw.

Mit jedem Versatz wächst die Zahl konstant um 6. Ich gehe also davon aus, dass es eine Regel geben sollte, die sich an diese Offsets anpasst. Ich kann das nicht genau herausfinden. Jemand?

algorithm grid hexagonal-grid Sidar
quelle

Antworten:

Ein Sechskantring mit dem Radius von N besteht aus 6 geraden Linien mit der Länge N - siehe mein äußerst grobes Beispiel unten :) Für N = 2:

Bildbeschreibung hier eingeben

Die Pfeile verdecken jeweils 2 Felder.

Ich gehe davon aus, dass Sie einige Funktionen haben, die Ihnen das benachbarte Plättchen in einer bestimmten Richtung geben, wie Nord (), Südost () usw. Ihr Algorithmus im Pseudocode sollte also ungefähr so aussehen:

var point = startingPoint.north(N)
for i = 0..N-1:
    result.add(point)
    point = point.southeast(1);
for i = 0..N-1:
    result.add(point)
    point = point.south(1);
for i = 0..N-1:
    result.add(point)
    point = point.southwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.northwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.north(1);
for i = 0..N-1:
    result.add(point)
    point = point.northeast(1);

Beachten Sie, dass dies auch für Kantenfälle funktionieren sollte, bei denen N = 1 ist und 6 Kacheln und N = 0 eine leere Menge zurückgeben.

Ich weiß, dass der Code nicht perfekt ist :) Hier gibt es einige Redundanzen. In meinen Projekten, in denen regelmäßig gekachelte Karten (sechseckig oder auf andere Weise) verwendet werden, habe ich normalerweise eine Aufzählung "Richtung", die es mir ermöglicht, dies reibungsloser zu tun:

var point = startingPoint.inDir(N, Direction.North)
var dir = Direction.SouthEast.
for d = 0..Direction.count():
    for i = 0..N-1:
        result.add(point)
        point = point.inDir(1, dir);
    dir = nextDirection(dir);

Liosan
quelle

Das sollte mich in die richtige Richtung bringen. Vielen Dank!

Sidar

Beachten Sie, dass das Codebeispiel doppelte Punkte für die ersten fünf Segmente hinzufügt. Es ist jedoch eine schöne Antwort.

MichaelHouse

@ Byte56 Ja, das habe ich mir gedacht. Aber zumindest sehe ich den Zusammenhang zwischen Richtungswechseln!

Sidar

@ Byte56 Wirklich? Hm. Ich habe versucht zu vermeiden, dass eins ... 0..N-1 0..1 für N = 2 ergibt, das ist also i = 0 und i = 1, was 2 Werten entspricht. 2 Werte aus jeweils 6 Richtungen sind 12 Kacheln, wie es sein sollte ...?

Liosan

Nee. Du hast recht. Da jede Schleife einen Punkt von der letzten Schleife hinzufügt, war ich für die Schleifen um eins versetzt, mein Fehler. Es ist ein kluger Algorithmus.

MichaelHouse

Ich habe festgestellt, dass dieser Artikel eine sehr gute Referenz für hexagonale Gitteralgorithmen ist, und sein Abschnitt über "Entfernungen" bietet eine Methode zum Bestimmen der Anzahl von Schritten zwischen zwei Kacheln. Wenn Sie Ihre Axialkoordinaten (xy) in Würfelkoordinaten (xyz) umwandeln , ist der Abstand immer gleich dem größten der Koordinatenversätze zwischen den beiden Kacheln oder max (| dx |, | dy |, | dz |).

Eine erschöpfende Suche des gesamten Rasters nach Kacheln im gewünschten Abstand ist mit den Rastermaßen, aber es ist eine einfache Implementierung, die sich gut für kleine Raster eignet. $O(n^2)$

KPM
quelle