Hilbert-Kurve: Raumfüllende Kurve

1 veranschaulicht, als Grenzkurve von Polygonzügen die Fläche eines Quadrats vollständig ausfüllt. Sie ist eine sogenannte FASS-Kurve, somit eine raumfüllende Kurve (engl. space-filling curve, abgekürzt SFC) und wurde 1891 von dem deutschen Mathematiker David Hilbert entdeckt. Die Möglichkeit, mit einer stetigen eindimensionalen Kurve ein zweidimensionales Gebiet komplett abdecken zu können, war den Mathematikern des neunzehnten Jahrhunderts neu (siehe auch Monsterkurve).

Die Hilbert-Kurve wird durch rekursive Iteration definiert und konstruiert. Die ${\displaystyle n}$-te Rekursionsstufe wird Hilbert-Kurve der ${\displaystyle n}$-ten Iteration, ${\displaystyle H_{n}}$, und der die Teilquadrate verbindende Polygonzug ${\displaystyle P_{n}}$ Hilbert-Polygon der ${\displaystyle n}$-ten Iteration genannt. Die Hilbert-Kurven und die Hilbert-Polygone endlicher Iterationen haben denselben Grenzwert, nämlich die Hilbert-Kurve im engeren Sinn. Die euklidische Länge des Hilbert-Polygons ${\displaystyle P_{n}}$ ist ${\displaystyle (4^{n}-1)\,2^{-n}=2^{n}-2^{-n}}$, das heißt, sie wächst mit der Nummer ${\displaystyle n}$ der Iteration über alle Grenzen. Die Hilbert-Kurve hat im Limes eine Hausdorff-Dimension von exakt 2, genau wie das Quadrat.

Mithilfe der Hilbert-Kurve endlicher Iteration kann man die Teilquadrate und mithilfe des Limes die Punkte im Quadrat in eine lineare Reihenfolge bringen, die Hilbert-Ordnung genannt wird. Mit ihr lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört binäres Suchen, binärer Suchbaum, Skip-Liste und andere.

Beim direkten Zugriff steht die Hilbert-Ordnung in Konkurrenz zu einem Zugriff, bei dem die linearen Ordnungen der Dimensionen in unterschiedlicher Rangigkeit zu einer lexikographischen Ordnung hintereinander geschaltet sind – im internen Speicher über ein mehrfach indiziertes Feld resp. im externen Speicher per wahlfreien Zugriff (Random Access). Wenn sich dies gut organisieren lässt, schneidet sie etwas schlechter ab. Sie ist aber überlegen, wenn es sich um eine ungefähre Suche handelt, an die sich eine sequentielle Suche anschließt, bei der Nachbarschaftsbeziehungen (engl. clustering) vorteilhaft ausgenutzt werden können. Dies ist bei ${\displaystyle d}$-dimensionalen Räumen ${\displaystyle \mathbb {R} ^{d}}$, bei denen Nachbarschaft durch die euklidische Metrik definiert ist, häufig der Fall – beispielsweise, wenn auf geographische Merkmale eines Objekts über die Schlüssel Länge und Breite zugegriffen werden soll. Die Hilbert-Kurve ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung. Bei der Z-Kurve ist die Rechnung geringfügig einfacher, aber die Nachbarschaftserhaltung deutlich schlechter.

Die Zuordnung ${\displaystyle h_{n}}$ der Hilbert-Kurve einer (endlichen) ${\displaystyle n}$-ten Iteration ist umkehrbar und kann zu beliebiger Feinheit gesteigert werden. Dieses und die gute Nachbarschaftserhaltung hat eine Vielfalt von Anwendungen der Hilbert-Kurve in der Informatik eröffnet, so in der Bildverarbeitung, Datendarstellung, im Hochleistungsrechnen und in anderen Gebieten.

•  
  Abb. 3a: 1. Iteration ${\displaystyle H_{1}}$  der Hilbert-Kurve
•  
  Abb. 3b: Hilbert-Kurve ${\displaystyle H_{2}}$  der 2. Iteration
•  
  Abb. 3c: Hilbert-Kurve ${\displaystyle H_{3}}$  der 3. Iteration
•  
  Abb. 3d: 3D-Hilbert-Kurven, 1. bis 3. Iteration

Die Abb. 3a bis 3c aus dem definierenden Artikel zeigen die drei ersten Iterationen der Hilbert-Kurve. Bei der ${\displaystyle n}$ -ten Iteration bringen ${\displaystyle 4^{n}}$  Nummern die ${\displaystyle 4^{n}}$  Intervalle (Teilstrecken der Linie oben in den Grafiken) und die ${\displaystyle 4^{n}}$  Quadrate mit gleichen Nummern zur Entsprechung. Die verstärkten polygonalen Linien ${\displaystyle P_{n}}$  bringen genau diese Reihenfolge der Quadrate heraus.

Eine nachfolgende Iteration verfeinert – bei Intervallen wie bei Quadraten – die Schachtelung um den Faktor 4.

Iterationsschritt

Die Konstruktion der Hilbert-Kurve als einer raumfüllenden Kurve

${\displaystyle {\begin{array}{llllll}h\;\colon &{\mathcal {I}}:=[0,1]:=\{t\mid 0\leq t\leq 1\}&\to &{\mathcal {I}}^{d}&=&\;\;[0,1]\times [0,1]\times \dotso \\&t&\mapsto &h(t)&=&(\;\;\;\underbrace {x\;\;\;\;,\;\;\;\;\,y\;\;\;\;,\;\dotso } _{d{\text{ Komponenten}}}\;\;\;)\\\end{array}}}$ 

beruht auf einem rekursiven Verfahren:

1. Das Verfahren beginnt mit dem (mehrdimensionalen Einheits-Intervall) ${\displaystyle [0,1]^{d}={\mathcal {I}}^{d}}$  als dem zu füllenden ${\displaystyle d}$ -dimensionalen Gebiet.
2. Jedes Gebiet wird aufgeteilt in ${\displaystyle 2^{d}}$  kongruente Teilgebiete (${\displaystyle d}$ -dimensionale Intervalle) der halben Seitenlänge und auf der Eingabeseite ein Intervall in ${\displaystyle 2^{d}}$  gleich lange Teilintervalle. Das Verfahren überführt damit 1D-Schachtelungen von Intervallen in 2D-Schachtelungen von Quadraten (oder in 3D-Schachtelungen von Würfeln), ist also inklusionserhaltend.
3. Für jedes Teilgebiet ist eine raumfüllende Kurve zu finden, die durch verkleinerte Verschiebung, Spiegelung und/oder Rotation der Vorgängerkurve gebildet wird.   (Prinzip der Selbstähnlichkeit)
4. Die Spiegelungs- und Rotationsoperationen lassen sich so wählen, dass sich die ${\displaystyle 2^{d}}$  Teilkurven zu einer einzigen gerichteten Kurve zusammenfügen.

Eine Hilbert-Kurve wird wesentlich durch die Reihenfolge charakterisiert, in der die Teilgebiete hintereinander aufgesucht (traversiert) werden. Mit wachsender Dimensionszahl ${\displaystyle d}$  wächst die Anzahl der unterschiedlichen Hilbert-Kurven, die sich dann auch in ihrer Nachbarschaftserhaltung stark unterscheiden können.

Dieser Artikel beschränkt sich fast ausschließlich auf die Dimensionszahl ${\displaystyle d=2}$ , also auf die Abbildung des Einheitsintervalls ${\displaystyle {\mathcal {I}}}$  auf das Einheitsquadrat ${\displaystyle {\mathcal {Q}}:={\mathcal {I}}^{2}}$ . Bei dieser Dimensionszahl treten alle einschlägigen mathematischen Phänomene bereits in Erscheinung.

Während die Hilbert-Kurve (auf der Ausgabeseite) ein „Teilquadrat“ durchläuft (füllt), soll auch der Parameter ${\displaystyle t}$  auf der Eingabeseite das ihm entsprechende Teilintervall durchlaufen. Dies entspricht der Vorgabe, dass die Hilbert-Kurve in allen Bereichen »gleich schnell« voranschreitet.

Um dies sicherzustellen, wird als Intervallschachtelung auf der Parameterseite die („4-adische“) Darstellung von ${\displaystyle t=:0_{4}.\!\tau _{1}\tau _{2}\tau _{3}\dotso \in {\mathcal {I}}}$  im Quaternärsystem mit ${\displaystyle \tau _{n}\in \{0,1,2,3\}}$  gewählt. Es sei ${\displaystyle t_{n}:=0_{4}.\!\tau _{1}\tau _{2}\dotso \tau _{n}}$  gesetzt, so dass

${\displaystyle \{t\mid t_{n}\leq t$     

ein Intervall in der ${\displaystyle n}$ -ten Schachtelung des Parameters ${\displaystyle t}$  ist. Auf der Seite des Quadrats (Ausgabeseite) werden die Koordinaten ${\displaystyle x=:0_{2}.\!\xi _{1}\xi _{2}\xi _{3}\dotso \in {\mathcal {I}}}$  und ${\displaystyle y=:0_{2}.\!\eta _{1}\eta _{2}\eta _{3}\dotso \in {\mathcal {I}}}$  im Binärsystem („2-adisch“) dargestellt mit ${\displaystyle \xi _{n},\eta _{n}\in \{0,1\}}$ . Die (abbrechenden) Koordinaten ${\displaystyle (x_{n},y_{n})\in {\mathcal {I}}^{2}={\mathcal {Q}}}$  mit ${\displaystyle x_{n}:=0_{2}.\!\xi _{1}\xi _{2}\dotso \xi _{n}}$  und ${\displaystyle y_{n}:=0_{2}.\!\eta _{1}\eta _{2}\dotso \eta _{n}}$  stehen dabei für das Teilquadrat, das diese Koordinaten zur linken unteren Ecke hat. Und die Folge der durch ${\displaystyle {\bigl (}(x_{n},y_{n}){\bigr )}_{n\in \mathbb {N} }}$  spezifizierten Quadrate, die die Seitenlänge ${\displaystyle 2^{-n}}$  und die Fläche ${\displaystyle 4^{-n}}$  haben, macht eine 2D-Intervallschachtelung in der Ebene aus. Diese ${\displaystyle d}$ D-Schachtelungen seien als die „Rasterschachtelung“ ${\displaystyle R:={\bigl (}R_{n}{\bigr )}_{n\in \mathbb {N} }}$  (der Hilbert-Kurve) bezeichnet.

Die ${\displaystyle n}$ -te Iteration ${\displaystyle H_{n}}$  der „Hilbert-Kurve“ ist eine geordnete Folge von ${\displaystyle 4^{n}}$  an genau einer Quadratseite mit dem Folgequadrat zusammenstoßenden Quadraten (oder deren linken unteren Eckpunkten resp. deren Mittelpunkten). Diese Folge wird am besten durch einen gerichteten Polygonzug von Quadratmittelpunkt

${\displaystyle {\bigl (}{\dot {x}}_{n}(t),{\dot {y}}_{n}(t){\bigr )}:={\bigl (}x_{n}(t)+2^{-n-1},y_{n}(t)+2^{-n-1}{\bigr )}}$ 

zu Quadratmittelpunkt (Parameter ${\displaystyle t^{\prime }:=t+4^{-n}}$ ) verdeutlicht. Dieser Polygonzug ${\displaystyle P_{n}}$  enthält alles Wichtige und wird häufig als das Hilbert-Polygon (engl. auch approximating curve und Hilbert pseudo curve) der ${\displaystyle n}$ -ten Iteration bezeichnet (Beispiele finden sich in den Hilbert-Kurven der 1. bis 3. Iteration der obigen Abbildungen).

Polygonzug

Im Folgenden wird gezeigt, wie die ${\displaystyle 4^{n}}$  Quadrate eines Rasters ${\displaystyle R_{n}}$  sämtlich in eine Reihenfolge ${\displaystyle 0,1,2,\dotso ,4^{n}-1}$  gebracht werden, derart, dass sie bei wachsendem ${\displaystyle n}$  immer kleiner werden, einander näher rücken und im Limes eine Kurve bilden.

Im Sinn des obigen Programms sei rekursiv angenommen, dass in einem Teilquadrat ${\displaystyle \in R_{n}}$  ein Kurvenpunkt der selbstähnlichen Hilbert-Kurve berechnet ist. Es geht nun darum, diesen Punkt (resp. dieses Teilquadrat) so zu den anderen drei Teilquadraten in das Quadrat ${\displaystyle \in R_{n-1}}$  zu holen, dass alle solche Punkte zusammen genommen eine zusammenhängende Kurve (resp. eine zusammenhängende Folge von Teilquadraten des Rasters ${\displaystyle R_{n}}$ ) ergeben. Eine solche Transformation lässt sich zerlegen in:

die Verkleinerung des Quadrats linear um den Faktor ${\displaystyle {\tfrac {1}{2}}}$ ,	(Skal)
eine (die Hilbert-Kurve charakterisierende) Parallelverschiebung und	(Parv)
eine Isometrie (= orthogonale Abbildung = Drehung und/oder Spiegelung).	(Ausr)

Für die Wahl der passenden Drehungen und/oder Spiegelungen ist die Festlegung hilfreich, wo ein Quadrat einer Rasterschachtelung ${\displaystyle R_{n}}$  von der Kurve betreten und wo es verlassen wird. Bei der Hilbert-Kurve sind dies die Ecken genau einer Quadratseite. Da es auch auf die Richtung und Orientierung ankommt, werde dieses Charakteristikum eines Quadrats im Raster mit dem Begriff „Ausrichtung“ (engl. orientation, state) versehen und die Ausrichtung „hoch—rechts—runter“ (in Koordinaten ${\displaystyle \scriptstyle {\underset {y}{\uparrow }}{\underset {x}{\rightarrow }}{\underset {y}{\downarrow }}}$  resp. die Strecke ${\displaystyle {(0,0){\underline {\color {Mulberry}\bullet \!\!\!\color {Green}\to }}(1,0)}}$  für „Eintritt links unten—Austritt rechts unten“) mit dem Buchstaben ${\displaystyle \mathbf {A} }$  gekennzeichnet.

Aber auch die bloße Platzierung des Teilquadrats hängt von der Ausrichtung ab. Ist das große Quadrat ${\displaystyle \in R_{n-1}}$  (links in der Abbildung 4) gemäß ${\displaystyle \mathbf {A} }$  ausgerichtet, dann wird bei der Hilbert-Kurve das Quadrat ${\displaystyle \in R_{n}}$  abhängig von der Quaternärziffer ${\displaystyle \tau =\tau _{n}}$  in eines der vier Teilquadrate platziert, und zwar platziert die Quaternärstelle ${\displaystyle \tau =0}$  nach links unten, ${\displaystyle \tau =1}$  nach links oben, ${\displaystyle \tau =2}$  nach rechts oben und ${\displaystyle \tau =3}$  nach rechts unten, also nach dem „Grundmuster“ (engl. base pattern oder basic pattern)  . Ein Grundmuster für die 3-dimensionale Hilbert-Kurve ist   (s. a. den Abschnitt Ausblick auf 3 Dimensionen).

Andere Ausrichtungen (als ${\displaystyle \mathbf {A} }$ , und auch Platzierungsmuster) lassen sich durch eine vorgeschaltete Isometrie aus der Diëdergruppe ${\displaystyle D_{4}}$  des Quadrats darstellen.

Die zur Herstellung des einfachen Zusammenhangs (und damit der Stetigkeit im Limes) erforderlichen Drehungen und/oder Spiegelungen sind ebenfalls Isometrien aus ${\displaystyle D_{4}}$  und zusammen mit der Platzierung auszuführen. Diese Kombination wird im folgenden Abschnitt unter dem Begriff „Transformation“ beschrieben.

Transformation der rekursiven Teilquadrate auf das Einheitsquadrat

 

Um den Wechsel der Ausrichtung von einer Iteration zur nächsten präzise zu erfassen, sei angenommen, dass beide Quadrate, das große (links in der Abbildung 4) wie das Teilquadrat (rechts) gleich, bspw. gemäß ${\displaystyle \mathbf {A} }$ , ausgerichtet sind.

Die benötigten vier Transformationen hängen von der Quaternärziffer ${\displaystyle \tau \in \{0,1,2,3\}}$  ab und seien mit ${\displaystyle T_{0},T_{1},T_{2}}$  und ${\displaystyle T_{3}}$  bezeichnet:

${\displaystyle T_{1}\ :=\ (x,y)\mapsto {\bigl (}{\tfrac {x}{2}},{\tfrac {y+1}{2}}{\bigr )}}$	${\displaystyle T_{2}\ :=\ (x,y)\mapsto {\bigl (}{\tfrac {x+1}{2}},{\tfrac {y+1}{2}}{\bigr )}}$
${\displaystyle T_{0}\ :=\ (x,y)\mapsto {\bigl (}{\tfrac {y}{2}},{\tfrac {x}{2}}{\bigr )}}$	${\displaystyle T_{3}\ :=\ (x,y)\mapsto {\bigl (}{\tfrac {2-y}{2}},{\tfrac {1-x}{2}}{\bigr )}}$

Alle Transformationen skalieren zunächst die übergebenen Koordinaten ${\displaystyle (x,y)}$  des Punktes mit dem Faktor ${\displaystyle {\tfrac {1}{2}}}$ , da die Teilquadrate die halbe Seitenlänge haben, und enthalten eine Verschiebung in das durch ${\displaystyle \tau }$  (s. o.) bestimmte Teilquadrat. Zudem ist von einer Transformation je nach Lage ggf. eine (von ${\displaystyle \tau }$  abhängige) Viertelrotation, Spiegelung, d. h. eine Kongruenzabbildung ${\displaystyle \in D_{4}}$  durchzuführen:

• Bei ${\displaystyle \tau \!=\!0}$  kommt die Transformation ${\displaystyle T_{0}}$  zum Zuge. Sie spiegelt ihr Argument an der »Hauptdiagonalen« (strichpunktiert in Abbildung 4), wodurch sich der Drehsinn des Quadrats ändert. Die Eintrittsecke ins Teilquadrat (links unten) bleibt erhalten.
  (Alle Übertritte von einem Quadrat zum nächsten sind in der Abbildung 7 als kurze blaugrüne Pfeile vom Grundmuster des einen Quadrats diagonal zur Austrittsecke und von der Eintrittsecke des anderen Quadrats diagonal zu dessen Grundmuster dargestellt.)
  Die Austrittsecke dieses Teilquadrats ist nachher links oben und führt zum nächsten Teilquadrat mit ${\displaystyle \tau \!=\!1}$ .
• Die Zielquadrate bei den Transformationen ${\displaystyle T_{1}}$  und ${\displaystyle T_{2}}$  haben dieselbe Ausrichtung ${\displaystyle \mathbf {A} }$  mit Eintrittsecke links unten und Austrittsecke rechts unten, daher ist keine Spiegelung (und keine Drehung) erforderlich. Jedoch wird die Kurve skaliert in je eines der oberen Teilquadrate verschoben.
  ${\displaystyle T_{1}}$  verschiebt bei ${\displaystyle \tau \!=\!1}$  die Kurve um ${\displaystyle {\tfrac {1}{2}}}$  in ${\displaystyle y}$ -Richtung, also ins linke obere Teilquadrat. ${\displaystyle T_{2}}$  verschiebt für ${\displaystyle \tau \!=\!2}$  die Kurve diagonal ins rechte obere Teilquadrat.
  Die Eintrittsecke des Teilquadrats mit ${\displaystyle \tau \!=\!1}$  fällt mit der Austrittsecke von ${\displaystyle \tau \!=\!0}$  und die Austrittsecke von ${\displaystyle \tau \!=\!1}$  mit der Eintrittsecke von ${\displaystyle \tau \!=\!2}$  zusammen.
• Die Transformation ${\displaystyle T_{3}}$  spiegelt für ${\displaystyle \tau \!=\!3}$  ihr Argument an der »Nebendiagonalen« (strichpunktiert in Abbildung 4), wodurch sich der Drehsinn des Quadrats ändert. Danach wird das gespiegelte Ergebnis um ${\displaystyle {\tfrac {1}{2}}}$  in ${\displaystyle x}$ -Richtung, also ins rechte untere Teilquadrat verschoben, so dass die Eintrittsecke rechts oben liegt – an der Stelle der Austrittsecke des vorangehenden Teilquadrats mit ${\displaystyle \tau \!=\!2}$  – und die Austrittsecke mit der Austrittsecke des Ausgangsquadrates übereinstimmt (rechts unten).

Ersichtlich sind die Punkte ${\displaystyle (x,y)}$  über die sie enthaltenden Quadrate in eine Reihenfolge gebracht, die der Reihenfolge der Intervalle des Parameters ${\displaystyle t}$  entspricht – sowohl bezüglich der 4 Teilquadrate ${\displaystyle \in R_{n}}$  als auch bei den Anschlüssen zwischen zwei Quadraten ${\displaystyle \in R_{n-1}}$ .

Dabei findet der Übertritt von einem Quadrat zum nachfolgenden Nachbarquadrat immer nur über eine gemeinsame Quadratseite statt (s. kurze blaugrüne Pfeile in der Abbildung 7), sodass sich beim Polygonzug ${\displaystyle P_{n}}$  von Quadratmittelpunkt zu Quadratmittelpunkt ausschließlich Teilstrecken gleicher Länge, der Seitenlänge, ergeben, die alle zu den Koordinatenachsen parallel und miteinander in einer linearen Kette verbunden sind – mit der offensichtlichen Konsequenz, dass die Hilbert-Kurve im Limes stetig ist. Die Teilstrecken des Polygons erfahren dabei nur Richtungswechsel ${\displaystyle \in \{-90^{\circ },0^{\circ },90^{\circ }\}}$ .

Die Abbildung 4 zeigt darüber hinaus, dass ausgehend von der Ausrichtung ${\displaystyle \mathbf {A} }$  zwei neue (absolute) Ausrichtungen ${\displaystyle \mathbf {D} }$  (:= „rechts—hoch—links“) und ${\displaystyle \mathbf {B} }$  (:= „links—runter—rechts“) hinzukommen, und die Abbildungen 7 und 5, dass nur noch eine weitere Ausrichtung (:= „runter—links—hoch“), genannt ${\displaystyle \mathbf {C} }$ , fehlt, so dass es bei insgesamt vier Ausrichtungen bleibt. Sie seien im Folgenden in der Menge ${\displaystyle \mathbf {V} :=\{\mathbf {A} ,\mathbf {B} ,\mathbf {C} ,\mathbf {D} \}}$  zusammengefasst. Die zugehörige Gruppe ${\displaystyle V}$  der benötigten Isometrien ist eine Untergruppe der Diedergruppe ${\displaystyle D_{4}}$  des Quadrats, wird erzeugt von der Drehung um 180° (Spiegelung am Quadratmittelpunkt) und einer Spiegelung an einer Diagonalen, hat also die Gruppenordnung vier, den Exponenten zwei und ist isomorph zur Kleinschen Vierergruppe.

 

In der Abbildung 5 ist das große Quadrat, das Quadrat der ${\displaystyle 0}$ -ten Iteration (= Quadrat des Rasters ${\displaystyle R_{0}}$ ), gemäß ${\displaystyle \mathbf {A} }$  ausgerichtet – und dementsprechend in seiner Mitte gekennzeichnet. Die relativen Ausrichtungen der Quadrate höherer Iterationen sind rekursiv von Iteration zu Iteration den Regeln dieses Abschnitts entsprechend entwickelt und die Ergebnisse als absolute Ausrichtungen im Zentrum der Quadrate eingetragen. Als solche sind sie auf die initiale (absolute) Ausrichtung, hier ${\displaystyle \mathbf {A} }$ , des Ausgangsquadrates bezogen. Die absolute Ausrichtung eines Quadrats ist also die Akkumulation (Komposition, Verkettung) der relativen Ausrichtungen aller seiner rekursiven Vorgänger mit der initialen Ausrichtung am Rekursionsanfang.

Bemerkung 1

Weil im vorstehenden Abschnitt das Quadrat der Iteration ${\displaystyle \in R_{n}}$  »zeitlich« vor dem großen Quadrat ${\displaystyle \in R_{n-1}}$  als »vorhanden« angesehen wird, könnte man anzunehmen versucht sein, dass die (Ausrichtungen der) großen Quadrate (links) der höherwertigen Ziffern durch diejenigen späterer Iterationen (rechts) beeinflusst würden. Das Gegenteil ist jedoch der Fall:

• Die absolute Ausrichtung des großen Quadrats beeinflusst (zusammen mit der Quaternärziffer ${\displaystyle \tau _{n}}$ ) direkt die absolute Ausrichtung des Teilquadrats.

Das kann man übrigens schon beim Zeichnen von Hilbert-Polygonen zweier aufeinander folgender Iterationen feststellen, spielt für die Umkehrbarkeit der ${\displaystyle h_{n}}$  (s. Abschnitt #Hilbert-Polygon) eine große Rolle und wirkt sich auf die (Art der) Stetigkeit von ${\displaystyle h}$  (s. Abschnitt #Hilbert-Kurve) aus. Diese Abhängigkeit ist in der tabellarischen Abbildung 7 und im gleichwertigen Übergangsdiagramm der Abbildung 8 für alle vier vorkommenden Varianten (= Ausrichtungen) herausgearbeitet. Eine darauf basierende explizite Rekursionsformel für ${\displaystyle h}$  wird im entsprechenden Abschnitt vorgestellt.

In diesem Kapitel wird mit ${\displaystyle n\in \mathbb {N} _{0}}$  die endliche Iterationsstufe bezeichnet, die Einheitsintervalle ${\displaystyle {\check {\mathcal {I}}}:={\mathcal {I}}\!\setminus \!\{1\}=[0,1[}$  und ${\displaystyle {\check {\mathcal {Q}}}}$  sind oben halboffen, und für ${\displaystyle m\in \mathbb {N} }$ , bspw. ${\displaystyle m=2^{n}}$  oder ${\displaystyle m=4^{n}}$ , ist

${\displaystyle {\mathcal {I}}_{m}:=\{0,{\tfrac {1}{m}},{\tfrac {2}{m}},\dotso ,1-{\tfrac {1}{m}}\}=\{0,1,2,\dotso ,m\!-\!1\}\cdot {\tfrac {1}{m}}\;\;\subset {\check {\mathcal {I}}}}$ 

eine diskrete Menge von ${\displaystyle m}$  Elementen.

Hilbert-Polygon

Die Zuordnung der Hilbert-Kurve ${\displaystyle H_{n}}$  der ${\displaystyle n}$ -ten Iteration ist

${\displaystyle {\begin{array}{lrlllll}h_{n}\;\colon &{\check {\mathcal {I}}}&\to &{\check {\mathcal {Q}}}&:=&\;\;{\check {\mathcal {I}}}&\times &{\check {\mathcal {I}}}\\&t&\mapsto &\displaystyle h_{n}(t)=h_{n}(t_{n})&=&{\bigl (}x_{n}(t)=x_{n}(t_{n})&,&y_{n}(t)=y_{n}(t_{n}){\bigr )}\,.\\\end{array}}}$ 

Das Bild ${\displaystyle h_{n}({\check {\mathcal {I}}})}$  ist eine diskrete Menge, und zwar ist

${\displaystyle h_{n}({\check {\mathcal {I}}})={\mathcal {I}}_{2^{n}}\times {\mathcal {I}}_{2^{n}}={{\mathcal {I}}_{2^{n}}}^{2}}$ .

Die Koordinaten ${\displaystyle {\bigl (}x_{n}(t),y_{n}(t){\bigr )}}$  stehen dabei für linke untere Ecken von Quadraten des Rasters ${\displaystyle R_{n}}$ . In graphischen Darstellungen wird die Reihenfolge der Quadrate, deretwegen ja der ganze Aufwand getrieben wird, am einfachsten durch Verbindungsstrecken zwischen den Quadraten sichtbar gemacht. Am deutlichsten wird diese Reihenfolge, wenn man statt der ${\displaystyle 4^{n}}$  Ecken die ${\displaystyle 4^{n}}$  Quadratmittelpunkte

${\displaystyle {\bigl (}{\dot {x}}_{n}(t),\,{\dot {y}}_{n}(t){\bigr )}:={\bigl (}x_{n}(t)+2^{-n-1},\;y_{n}(t)+2^{-n-1}{\bigr )}\qquad \qquad (t\in {\mathcal {I}}_{4^{n}})}$ 

nimmt, weil die Verbindungsstrecken verschiedener Iterationsstufen dann getrennt bleiben und Symmetrien klarer herauskommen. Dieser Polygonzug in der Ebene von Quadratmittelpunkt zu Quadratmittelpunkt wird häufig als das Hilbert-Polygon ${\displaystyle P_{n}}$  der ${\displaystyle n}$ -ten Iteration bezeichnet.

Die diskrete Funktion ${\displaystyle {\hat {h}}_{n}:=h_{n}\!\mid _{{\mathcal {I}}_{4^{n}}}}$ , d. i. die Einschränkung von ${\displaystyle h_{n}}$  auf die diskrete Menge ${\displaystyle {\mathcal {I}}_{4^{n}}}$ , ist umkehrbar und hat die Umkehrfunktion ${\displaystyle {\hat {k}}_{n}}$ , die im Abschnitt Hilbert-Index behandelt wird. Nach Konstruktion ist ferner

${\displaystyle {\hat {h}}_{n}(t\pm 4^{-n})\;\;\,=\;\;\,{\begin{cases}{\hat {h}}_{n}(t)\pm (2^{-n}\!\!\!\!\!\!&,\!\!\!\!\!\!&0&)\\{\hat {h}}_{n}(t)\pm (0&,&2^{-n}\!\!\!\!\!\!&)\,,\end{cases}}}$ 

woraus die Implikation

${\displaystyle |t-t^{\prime }|\leq 4^{-n}\Longrightarrow {\bigl |}{\hat {h}}_{n}(t)-{\hat {h}}_{n}(t^{\prime }){\bigr |}\leq 2^{-n}}$ 

(und im Limes die gleichmäßige Stetigkeit) folgt.

Das Hilbert-Polygon ${\displaystyle P_{n}}$  ist eine einfache Kurve mit Anfang, Ende und ohne Berührungen oder Überschneidungen. Wie in der Einleitung erwähnt, hat es die euklidische Länge ${\displaystyle (4^{n}-1)\,2^{-n}=2^{n}-2^{-n}}$ , die also mit ${\displaystyle n}$  über alle Grenzen wächst. Alle Hilbert-Polygone derselben Iteration ${\displaystyle n}$  sind einander ähnlich.

Die Animation der nebenstehenden Abb. 6 gibt einen Eindruck, wie lang die Wege in höheren Iterationen werden. Sie deutet auch an, wie das Hilbert-Polygon nach und nach den ganzen Ersten Quadranten der ${\displaystyle (x,y)}$ -Ebene ausfüllen könnte: Wenn ein Quadrat fertig ist, dann ist der Polygonzug in der Richtung weg vom Ursprung fortzusetzen.

Die Bild- und die Definitionsmenge von ${\displaystyle {\hat {h}}_{n}}$  lassen sich aufgrund ihrer Diskretheit in einfacher Weise so skalieren, dass sie ganzzahlig werden.

Bei den beiden folgenden Algorithmen t2xyR und t2xyI und beim Algorithmus xy2tR erfolgt die Auswertung (Hintereinanderausführung) der verketteten Transformationen wie bei Operatoren üblich rechts-assoziativ, also von rechts nach links. Innerhalb des Programms findet die Auswertung im rekursiven Aufstieg – also »auf dem Rückweg« (im hinteren Abschnitt) – statt, weshalb die Auswertungsrichtung als »fein zu grob« zu charakterisieren ist. Damit sich bei dieser Auswertungsrichtung überhaupt etwas ergibt, muss der »Hinweg« abgebrochen werden. Beim wie immer gearteten Abbruchkriterium (im Pseudocode t2xyR formuliert mit der Genauigkeitsvariablen eps) wird der Punkt ${\displaystyle (x,y)}$ , wie in der Abb. 4 dargestellt, in dasjenige Rasterquadrat gebracht, das dem eingegebenen Teilintervall von ${\displaystyle t}$  entspricht, und dieses Vorgehen wird wiederholt bei jedem iterativen Schritt zurück.

Bemerkung 2

Wie weiter oben schon bemerkt, suggeriert die Abb. 4 eine solche Auswertungsrichtung. Gleichwohl existiert eine Abhängigkeit des ${\displaystyle n}$ -ten Quadrats von Teilen der ${\displaystyle (n+1)}$ -sten oder höherer Iterationsstufe überhaupt nicht, weder hinsichtlich der Ziffern ${\displaystyle \tau _{\nu }}$  (mit ${\displaystyle \nu >n}$ ) des Parameters ${\displaystyle t}$  noch hinsichtlich der Ziffern ${\displaystyle (\xi _{\nu },\eta _{\nu })}$  der Koordinaten ${\displaystyle (x,y)}$  noch hinsichtlich der Ausrichtung der Quadrate. Wenn es eine Rekursion gibt, dann kann sie in der Richtung von »grob zu fein« aufgesetzt werden, bei der die Auswertung im rekursiven Abstieg erfolgt. Die hieraus hervorgehende Rekursionsformel hat den Vorteil, dass ein »Abbruchkriterium« nicht gebraucht wird. (Ein Ergebnis liegt bei einem Abbruch unmittelbar vor – einschließlich einer Angabe über die möglicherweise eingegangene Ungenauigkeit.) Sie zählt damit zu den potentiell unendlichen Verfahren und wird im Abschnitt #Explizite Rekursionsformel beispielhaft vorgestellt. Der einzige erkennbare Nachteil ist, dass die Eigenschaft der Ausrichtung eines Quadrats explizit gemacht werden muss und nicht in den Formeln für die Transformationen versteckt werden kann.

Rekursiver Algorithmus

Der nachfolgende Pseudocode t2xyR implementiert rekursiv die Abb. 4 mit ${\displaystyle \mathbf {A} }$  als Ausrichtung für Zwischen- wie Endergebnis. Er nimmt als Argument einen Parameter ${\displaystyle t\in {\check {\mathcal {I}}}}$  und eine Begrenzung eps${\displaystyle :=2^{-n}}$  der Iterationstiefe. Zurückgegeben werden die Koordinaten der linken unteren Ecke eines Quadrates der ${\displaystyle n}$ -ten Iteration.

Eingabe:	Parameter ${\displaystyle t\in {\check {\mathcal {I}}}}$
Ausgabe:	Koordinaten ${\displaystyle x,y\in {\check {\mathcal {I}}}}$
Auswertungsrichtung:	fein zu grob

 function t2xyR(t, eps) begin    if eps > 1 then      return (0, 0); // im Ergebnisquadrat die linke untere Ecke    else      q = floor(4*t);      // Die Quaternärstelle q ∈ {0, 1, 2, 3} bestimmt,      //   in welches Teilquadrat der Punkt gehört      //   und wie er zu transformieren ist.      r = 4*t − q;      (x,y) = t2xyR(r, eps*2); // r ∈ I ↦ (x,y) ∈ Q      switch q do        case 0: return (y/2,         x/2);        case 1: return (x/2,         y/2 + 1/2);        case 2: return (x/2 + 1/2,   y/2 + 1/2);        case 3: return (1−eps − y/2, 1/2−eps − x/2);      end switch    end if  end function 

 

Iterativer Algorithmus mit ganzzahligen Ein-/Ausgabewerten

Bei der folgenden iterativen Lösung ist ${\displaystyle n}$  die Nummer der Iteration und ${\displaystyle p:=2^{n}}$  die Anzahl der 1D-Teilintervalle. Zurückgegeben wird die linke untere Ecke eines Quadrats. Der folgende Pseudocode t2xyI hat ganzzahlige Ein-/Ausgabe (d. h. es wird nicht auf Einheitsintervall oder -quadrat skaliert).

Eingabe:	Parameter ${\displaystyle t\in \{0,1,\dotso ,p^{2}-1\}}$
Ausgabe:	Koordinaten ${\displaystyle x,y\in \{0,1,\dotso ,p-1\}}$
Auswertungsrichtung:	fein zu grob

 function t2xyI(t, p) begin    (x, y) = (0, 0); // im Ergebnisquadrat die linke untere Ecke    for (m = 1; m < p; m *= 2) do // m wächst exponentiell      rx = 1 & t/2;      // Binärziffer[1]: 0=links/1=rechts      ry = 1 & (t ^ rx); // Binärziffer[0]      (x, y) = rot(x, y, rx, ry, m);      x += m * rx;      y += m * ry;      t /= 4; // zur nächsten Quaternärziffer    end for  return (x, y);  end function  // Drehspiegelung eines Quadrates  function rot(x, y, rx, ry, p) begin    if (ry == 0) then      if (rx == 1) then        x = p−1 − x;        y = p−1 − y;      end if      // vertausche x und y      z = x;      x = y;      y = z;    end if  return (x, y);  end function 

Hierbei kommen die C-Operatoren ^ für bitweises XOR, & für bitweises UND, += für Inkrementieren, *=2 für Verdoppeln und /=2 für Halbieren zum Einsatz.

In der Funktion t2xyI bedeutet die Variable rx das Übereinstimmen des vorletzten Bits bei x und t; analog für ry und y mit dem letzten Bit.

Die Funktion (und ihre Umkehrung s. u.) benutzen die Funktion rot, um die Koordinaten x und y in einem Teilquadrat so zu spiegeln und zu drehen, dass die Teilstücke konsekutiv (stetig) zusammengefügt werden.

Explizite Rekursionsformel

Eingabe:	Parameter ${\displaystyle t\in {\check {\mathcal {I}}}}$
Ausgabe:	Koordinaten ${\displaystyle x,y\in {\check {\mathcal {I}}}}$
Auswertungsrichtung:	grob zu fein

Ist ${\displaystyle t=:0_{4}.\!\tau _{1}\tau _{2}\tau _{3}\dotso \in {\check {\mathcal {I}}}}$  eine 4-adische Darstellung des Parameters, dann lässt sich die (unendliche) Folge ${\displaystyle {\bigl (}h_{n}(t){\bigr )}_{n\in \mathbb {N} }={\Bigl (}{\bigl (}x_{n}(t),y_{n}(t){\bigr )}{\Bigr )}_{n\in \mathbb {N} }}$  auch als Rekursion über die Quadratmittelpunkte

${\displaystyle {\bigl (}{\dot {x}}_{n}(t):=x_{n}(t)+2^{-n-1},\;\;{\dot {y}}_{n}(t):=y_{n}(t)+2^{-n-1}{\bigr )}}$ 

und die „absolute“ Ausrichtung ${\displaystyle a_{n}}$  mit dem Rekursionsanfang

${\displaystyle {\dot {x}}_{0}(t)={\tfrac {1}{2}}}$	und
${\displaystyle {\dot {y}}_{0}(t)={\tfrac {1}{2}}}$	und
${\displaystyle a_{0}(t)=\mathbf {A} }$	Ausrichtung am Rekursionsanfang (= initiale Ausrichtung)

und dem Rekursionsschritt

${\displaystyle {\dot {x}}_{n}(t)}$	${\displaystyle ={\dot {x}}_{n-1}(t)+2^{-n-1}(2X_{a_{n-1}(t),\,\tau _{n}}-1)}$	(RFh_ξ),
${\displaystyle {\dot {y}}_{n}(t)}$	${\displaystyle ={\dot {y}}_{n-1}(t)\ +2^{-n-1}(2Y_{a_{n-1}(t),\,\tau _{n}}-1)}$	(RFh_η) und
${\displaystyle a_{n}(t)}$	${\displaystyle =A_{a_{n-1}(t),\,\tau _{n}}}$	(RFh_a)

für ${\displaystyle n\in \mathbb {N} }$  schreiben. Die drei (4×4)-Matrizen

${\displaystyle X:=\left[{\begin{smallmatrix}{\begin{array}{rrrr}0&0&1&1\\1&0&0&1\\1&1&0&0\\0&1&1&0\end{array}}\end{smallmatrix}}\right]\!,\,Y:=\left[{\begin{smallmatrix}{\begin{array}{rrrr}0&1&1&0\\1&1&0&0\\1&0&0&1\\0&0&1&1\end{array}}\end{smallmatrix}}\right]\!,\;A:=\left[{\begin{smallmatrix}{\begin{array}{rrrr}\mathbf {D} &\mathbf {A} &\mathbf {A} &\mathbf {B} \\\mathbf {C} &\mathbf {B} &\mathbf {B} &\mathbf {A} \\\mathbf {B} &\mathbf {C} &\mathbf {C} &\mathbf {D} \\\mathbf {A} &\mathbf {D} &\mathbf {D} &\mathbf {C} \end{array}}\end{smallmatrix}}\right]\;\;{\begin{smallmatrix}{\begin{array}{ll}\leftarrow &\mathbf {A} \\\leftarrow &\mathbf {B} \\\leftarrow &\mathbf {C} \\\leftarrow &\mathbf {D} \end{array}}\end{smallmatrix}}\!\!\!\left.{\begin{array}{c}\,\\[13pt]\,\end{array}}\right\rbrace \scriptstyle \;=\;a}$ 

sind äquivalent zu den vier Übersetzungstabellen der Abbildung 7. Sie werden an ihrem ersten Index, dem Zeilenindex, durch die absolute Ausrichtung ${\displaystyle a_{n-1}(t)\in \mathbf {V} :=\{\mathbf {A} ,\mathbf {B} ,\mathbf {C} ,\mathbf {D} \}}$  indiziert. Das Ergebnis ist bei ${\displaystyle X}$ , ${\displaystyle Y}$  und ${\displaystyle A}$  jeweils eine vierstellige Zeile, die zusammen genommen eine der Übersetzungstabellen darstellen. Jede Stelle (Spalte) einer solchen Zeile wird durch die Quaternärziffer ${\displaystyle \tau _{n}\in \{0,1,2,3\}}$  indiziert. Daraus resultiert (Gl.n RFh_ξ und RFh_η) das neue Ziffernpaar ${\displaystyle (\xi _{n},\eta _{n})}$  für den Punkt ${\displaystyle (x,y)}$  und (Gl. RFh_a) die neue absolute Ausrichtung.

Die Folge ${\displaystyle {\bigl (}({\dot {x}}_{n},{\dot {y}}_{n}){\bigr )}_{n\in \mathbb {N} }}$  der Quadratmittelpunkte mit ${\displaystyle {\dot {x}}_{n}:=0_{2}.\!\xi _{1}\xi _{2}\dotso \xi _{n}+2^{-n-1}}$  und ${\displaystyle {\dot {y}}_{n}:=0_{2}.\!\eta _{1}\eta _{2}\dotso \eta _{n}+2^{-n-1}}$ , steht für die 2D-Intervallschachtelung

${\displaystyle {\begin{array}{lllll}&{\bigl (}[{\dot {x}}_{n}-2^{-n-1},&{\dot {x}}_{n}+2^{-n-1}]&\times \;[{\dot {y}}_{n}-2^{-n-1},&{\dot {y}}_{n}+2^{-n-1}]{\bigr )}_{n\in \mathbb {N} }\\=&{\bigl (}[x_{n},&x_{n}+2^{-n}]&\times \;[y_{n},&y_{n}+2^{-n}]{\bigr )}_{n\in \mathbb {N} },\\\end{array}}}$ 

die ${\displaystyle h(t)}$  zum Limes hat.