Konvertieren zwischen Spiral Honeycomb Mosaic und axialen Hex-Koordinaten

Es scheint ziemlich logisch zu sein, mit hexagonalen Gittern umzugehen, die ein System von Axialkoordinaten wie das hier beschriebene verwenden .

Beim Lesen über Hex-Gitter bin ich jedoch auf den Begriff des Spiral Honeycomb Mosaic gestoßen (die Links auf diesem Spiegel sind defekt; der Inhalt wird von hier aus etwa auf halber Höhe der Seite kopiert ). Es scheint hauptsächlich in der Bildverarbeitung verwendet zu werden, aber es ist vom Standpunkt aus interessant, dass es jedem Hex eine eindeutige, fortlaufende Basis-7-Nummer als Kennung zuweist.

Ich bin mir nicht sicher, ob es tatsächlich für irgendetwas nützlich ist , aber ich frage mich: Ist es möglich, zwischen dem SHM-Nummerierungssystem und den Axialkoordinaten hin und her zu konvertieren?

Beide Systeme haben Methoden, um von einem Hex in die kartesischen Koordinaten seines Zentrums umzuwandeln, so dass man dies vermutlich aus einem System heraus und dann in das andere berechnen könnte. Aber das ist chaotisch und ineffizient, und ich bin überzeugt, dass es möglich ist, es besser zu machen.

Aufgrund der fraktalen Natur des SHM beruht die Konvertierungsroutine im bereitgestellten Beispielcode auf einer Schleife. es scheint, als ob die allgemeine Lösung eine Reihe beinhalten könnte?

Danke für ein faszinierendes Puzzle! Ja, es sieht so aus, als könnten wir es besser machen als eine Konvertierung durch kartesische Koordinaten von Sechseckzentren. Es kann vollständig mit ganzzahliger Mathematik durchgeführt werden, obwohl ich unten in einer Matrix ein Rational eingefügt habe, um die Notation kurz zu halten.

Sie haben Recht, dass sowohl der Kodierungs- als auch der Dekodierungsprozess Schleifen erfordern. Glücklicherweise benötigen die Schleifen, da SHM um Größenordnungen arbeitet, nie mehr als Log_7 (n + 1) -Iterationen, wobei n die Anzahl der Kacheln im Raster ist, was sehr vernünftig ist.

Um meine Notation symmetrisch zu halten, habe ich mich für ein 3-Koordinaten-Raster wie das folgende entschieden (was Ihr Beispiel aus Red Blob Games "Würfelkoordinaten" nennt ). Wenn Sie möchten, können Sie die z-Koordinate weglassen und alle Instanzen von .z durch - (x + y) ersetzen, um stattdessen "Axialkoordinaten" zu erhalten.

Aus Gründen der Geschwindigkeit und Sauberkeit des Codes empfehle ich die Verwendung von Nachschlagetabellen zum Codieren und Decodieren. Zum Dekodieren von SHM in Würfelkoordinaten können Sie zunächst die Tabelle mit den folgenden Wiederholungen erstellen:

Rotate(v) = (-v.z, -v.x, -v.y)

Decode[,] = 2D array of ordered triples, [7 x (max_order_of_magnitude + 1)]

Decode[0, k] = (0, 0, 0) for all k = 0...max_order_of_magnitude
Decode[1, 0] = (0, -1, 1)

Decode[d + 1, k] = Rotate(Decode(d, k)) for d = 2...6, all k
Decode[d, k + 1] = Decode(d, k) + 2 * Rotate(Decode(d, k)) for all d, k

Dann wird das Dekodieren extrem einfach:

SHMToPoint(code)
{
    point = (0, 0, 0)
    order = 0    

    while(code > 0)
    {
        digit = code % 7
        point += Decode(digit, order)
        code = floor(code/7)
        order++
    }
    return point
}

Dies funktioniert, weil in der ersten Zeile der Tabelle die Offsets der Zellen gespeichert sind, die durch die Ziffern 0, 1, 2, 3, 4, 5, 6 codiert sind. In der nächsten Zeile werden die Offsets für 0, 10, 20, 30, 40, 40 gespeichert. 50, 60 und so weiter. Durch Summieren der Offsets, die durch jede Größenordnung beigetragen werden, können Sie jeden Punkt innerhalb des Bereichs der Tabelle decodieren.

Ich denke, dass die folgende Methode für die Codierung funktioniert, aber ich gebe zu, dass ich sie nicht getestet habe. Es wird eine viel einfachere Nachschlagetabelle verwendet:

Encode = [0, 5, 1, 6, 3, 4, 2]

und eine Rotations- und Skalierungsmatrix:

Untwist = | 5  -4   2 |
          | 2   5  -4 |
          |-4   2   5 | * 1/21

Um eine Würfelkoordinate in SHM zu codieren, dann ...

PointToSHM(point)
{
    code = 0
    magnitude = 1
    while(point != (0, 0, 0))
    {
        digitIndex = (((point.x - 2 * point.y) % 7) + 7) % 7
        code += magnitude *Encode[digitIndex]
        point = Untwist * (point - Decode[digit, 0])
        // treating "point" as a column vector, and rounding if necessary
        magnitude *= 7
    }
    return code
}

Beachten Sie, dass der hier generierte (und oben decodierte) Code im numerischen Standardformat vorliegt (dh der im SHM-Diagramm mit "10" gekennzeichneten Zelle wird ein Code von 7 in Basis 10 oder 111 in Binärform zugewiesen). Wenn Sie es in Base 7 anzeigen möchten, müssen Sie beim Konvertieren in eine Zeichenfolge den entsprechenden Radix verwenden.

Dies funktioniert, indem bei jeder Iteration die niedrigstwertige Ziffer des SHM-Codes ermittelt wird (unter Verwendung der Tatsache, dass sich diese Ziffern so wiederholen, dass die Ebene regelmäßig gekachelt wird - die LUT ist die Folge von Ziffern, die aus (0, 0, 0) gelesen werden. bis (6, 0, -6), der sich in jeder Zeile mit einem Versatz wiederholt). Als nächstes wird diese Ziffer effektiv auf Null gesetzt, indem der entsprechende Versatz früher von unserer Dekodierungstabelle subtrahiert wird, und das Fraktal wird mithilfe der Untwist-Matrix um eine Ebene verkleinert. Dies wirkt wie eine Rechtsverschiebung in Basis 7 in geometrischer Form - es bringt die nächste Ziffer an die niedrigstwertige Position und bringt die Zelle "10" auf "1" usw., wo wir den gleichen Trick erneut verwenden können, um das zu lesen Ziffer in der nächsten Schleife.

Ich hoffe das funktioniert bei dir!