DE 
EnglishDefault
Українська
Polski
Español
日本語
Italiano
Português (BR)
Français
العربية
Nederlands
中文
한국어
हिन्दी
Türkçe
Tiếng Việt
Русский
Bahasa Indonesia
فارسی
বাংলা
ไทย
Filipino
Kiswahili
اردو
Bahasa Melayu
தமிழ்
עברית
Ελληνικά
ਪੰਜਾਬੀ
አማርኛ
မြန်မာဘာသာ
ខ្មែរ
ქართული
नेपाली
Монгол хэл
Հայերեն
සිංහල
ລາວ
Čeština
Română
Magyar
Български
Svenska
Dansk
Suomi
Norsk
Slovenčina
Hrvatski
Српски
Slovenščina
Lietuvių
Latviešu
Eesti
Íslenska
Shqip
Македонски
Bosanski
Malti
Azərbaycanca
Қазақша
O'zbekcha
Тоҷикӣ
Кыргызча🌀 Raumfüllende Kurven
Interaktive raumfüllende Kurven: konstruieren Sie echte Hilbert-, Peano- und Z-Order/Morton-Kurven, färben Sie nach Pfadposition und erkunden Sie die Abbildung von d auf (x,y) sowie die Lokalität.
Über die Hilbert-Kurve
Die Hilbert-Kurve ist ein stetiges raumfüllendes Fraktal, das 1891 von David Hilbert eingeführt wurde. Bei jeder Iteration n durchläuft die Kurve jede Zelle eines 2ⁿ × 2ⁿ-Gitters genau einmal, und im Grenzfall durchläuft sie jeden Punkt des Einheitsquadrats — was ihr eine fraktale Dimension von genau D = 2 verleiht, die der Ebene selbst entspricht, obwohl es sich um einen einzigen stetigen eindimensionalen Pfad handelt. Ihre wichtigste Eigenschaft ist die Bewahrung der Lokalität: Punkte, die entlang des 1D-Kurvenindex nahe beieinander liegen, werden tendenziell auf Punkte abgebildet, die im Raum nahe beieinander liegen, was sie weit überlegen macht gegenüber zeilen- oder spaltenweisen Scans für cache-freundlichen Speicherzugriff und geografische Indizierung. Dieselbe Konstruktion verallgemeinert sich auf drei Dimensionen und fädelt einen einzigen Pfad durch jede Zelle eines 2ⁿ × 2ⁿ × 2ⁿ-Würfels — was diese Simulation in echtem 3D darstellt.
Diese Simulation konstruiert die 3D-Hilbert-Kurve von Ordnung 1 bis Ordnung 5, färbt den Pfad nach Fortschritt, sodass Sie den raumfüllenden Sweep verfolgen können, und lässt Sie die Struktur frei umkreisen. Sie können die Kurve nachzeichnen oder durch ihren Zeichenfortschritt scrubben, um genau zu sehen, wie die 1D-Ordnung auf das 3D-Gitter abgebildet wird.
Häufig gestellte Fragen
Was macht die Hilbert-Kurve „raumfüllend"?
Eine raumfüllende Kurve ist eine stetige surjektive Abbildung eines Liniensegments auf eine höherdimensionale Region. Die Hilbert-Kurve ist der Grenzwert einer Folge stückweise linearer Approximationen; bei jeder Ordnung n durchläuft die Kurve alle Zellen des Gitters (4ⁿ in 2D, 8ⁿ in 3D), und wenn n → ∞, wird der Pfad im Würfel dicht — jeder Punkt ist ein Grenzwert von Kurvenpunkten. Kontraintuitiv bedeutet dies, dass ein 1D-Objekt eine höherdimensionale Region ohne Volumen „füllen" kann, weil „füllen" hier Dichte bedeutet, nicht Maß.
Wie bewahrt die Hilbert-Kurve die Lokalität?
Für eine Hilbert-Kurve der Ordnung n gilt: Wenn sich zwei 1D-Indizes d₁ und d₂ um 1 unterscheiden, unterscheiden sich ihre entsprechenden Koordinaten um genau eine Zelle. Formaler ausgedrückt wächst der maximale räumliche Abstand zwischen zwei Punkten mit Indizes innerhalb des Abstands k entlang der 1D-Kurve viel langsamer als der O(k)-Worst-Case für zeilenweise Scans. Diese Lokalitätseigenschaft wird bei der räumlichen Datenbankindizierung, cache-obliviösen CPU-Algorithmen und Bilddithering genutzt.
Wofür wird die Hilbert-Kurve in der Informatik verwendet?
Die primären Anwendungen sind räumliche Datenbankindizierung (z. B. verwendet GeoHash eine Z-Order-Variante; PostGIS verwendet Hilbert-Ordnung für BRIN-Indizes), cache-obliviöse Matrixoperationen, Lastverteilung bei paralleler Berechnung auf Gittern und fraktale Bildkompression. Die Kurve wird gegenüber Z-Order (Morton) bevorzugt, weil sie keine diagonalen Sprünge macht — jeder Schritt bewegt sich zu einer benachbarten Zelle — was in 2D und 3D eine glattere räumliche Lokalität ergibt.
Wie wird die 3D-Hilbert-Kurve konstruiert?
Die 3D-Hilbert-Kurve unterteilt einen Würfel rekursiv in 8 Teilwürfel und besucht sie in einer Gray-Code-Reihenfolge, sodass aufeinanderfolgende Teilwürfel eine Fläche teilen. Jeder Teilwürfel ist selbst eine kleinere Hilbert-Kurve, aber gedreht und gespiegelt, sodass ihr Eintrittspunkt den Austritt des vorherigen Teilwürfels berührt und ihr Austritt mit dem nächsten übereinstimmt. Die Standardimplementierung wendet diese Rotationen pro Oktant rekursiv an (oder verwendet äquivalent Skillings Transpose/Gray-Code-Algorithmus), um die Abbildung Index → (x, y, z) für alle 8ⁿ Zellen zu erzeugen.
Was ist der Unterschied zwischen der Hilbert- und der Peano-Kurve?
Beide sind raumfüllende Kurven, unterteilen sich aber unterschiedlich. Die Hilbert-Kurve teilt jedes Quadrat in 4 Teilquadrate (Basis-2-Gitter) und verwendet einen U-förmigen Pfad mit zwei Spiegelungen bei jedem Schritt. Die Peano-Kurve unterteilt in 9 Teilquadrate (Basis-3-Gitter) mit einem S-förmigen Scan und war die erste veröffentlichte raumfüllende Kurve (Giuseppe Peano, 1890 — ein Jahr vor Hilbert). Hilberts Version wird in der Informatik generell bevorzugt, weil das Zweierpotenz-Gitter sich natürlich an binäre Adressierung anpasst.
Was ist die Z-Order-(Morton-)Kurve und wie schneidet sie im Vergleich ab?
Die Z-Order- oder Morton-Kurve wird konstruiert, indem die binären Darstellungen der Koordinaten verschachtelt werden. Sie ist extrem schnell zu berechnen — erfordert nur Bit-Verschachtelungsoperationen — und wird in vielen räumlichen Indizes verwendet, einschließlich S2-Geometrie und einigen GPU-Textur-Layouts. Sie hat jedoch einen Lokalitätsnachteil: sie macht diagonale Sprünge zwischen Quadranten, sodass Cluster nahe beieinanderliegender Punkte häufiger auf weit auseinanderliegende 1D-Indizes abgebildet werden können als bei der Hilbert-Kurve.
Welche fraktale Dimension hat die Hilbert-Kurve?
Die Hausdorff-(fraktale) Dimension der 2D-Hilbert-Kurve ist genau 2; für die 3D-Hilbert-Kurve ist sie genau 3. Dies wird aus der Selbstähnlichkeit berechnet: in 3D ersetzt jeder Schritt ein Segment durch 8 skalierte Kopien im Faktor 1/2, sodass D = log(8)/log(2) = 3. Eine Dimension gleich dem Einbettungsraum bedeutet, dass die Kurve so „raumfüllend" ist wie diese Region, obwohl sie im Sinne des Lebesgue-Maßes weiterhin ein Volumen von null hat.
Wie viele Punkte enthält die 3D-Kurve bei jeder Ordnung?
Bei Ordnung n besucht die 3D-Hilbert-Kurve jede Zelle eines 2ⁿ × 2ⁿ × 2ⁿ-Gitters, sie hat also 8ⁿ Punkte, verbunden durch 8ⁿ − 1 Segmente. Ordnung 1 hat 8 Punkte, Ordnung 2 hat 64, Ordnung 3 hat 512, Ordnung 4 hat 4.096, und Ordnung 5 hat 32.768 Punkte. Diese Simulation begrenzt die Ordnung auf 5, um die Anzahl der Eckpunkte und die Rendering-Leistung im Browser vernünftig zu halten.
Ist die Hilbert-Kurve wirklich stetig?
Ja — die Hilbert-Kurve ist eine mathematisch bewiesene stetige Funktion von [0, 1] auf das Einheitsquadrat (oder den Würfel in 3D). Der Beweis nutzt die Tatsache, dass jede endliche Ordnungs-Approximation gleichmäßig stetig ist und die Folge gleichmäßig konvergiert, sodass die Grenzfunktion nach dem Satz vom gleichmäßigen Grenzwert ebenfalls stetig ist. Die Grenzkurve ist jedoch nirgends differenzierbar — sie hat an keinem Punkt eine Tangente — was sie zu einem Beispiel für eine stetige, aber nirgends differenzierbare Funktion macht.
Beobachten Sie, wie Hilbert-, Peano- und Morton-(Z-Order)-Kurven die Ebene füllen. Färben Sie nach Pfadposition, um zu sehen, wie die Hilbert-Kurve die Lokalität weit besser bewahrt als Z-Order, und untersuchen Sie die 1D↔2D-Abbildung.
3D · Three.js / WebGL-Renderer · Ziel 60 FPS · läuft vollständig clientseitig, keine Installation nötig