PL 
EnglishDomyślny
Українська🌀 Krzywe wypełniające przestrzeń
Zobacz, jak krzywe Hilberta, Peana i Mortona (Z-order) wypełniają płaszczyznę. Koloruj według pozycji na ścieżce, by przekonać się, o ile lepiej krzywa Hilberta zachowuje lokalność niż Z-order, i przeanalizuj odwzorowanie 1D↔2D.
O krzywej Hilberta
Krzywa Hilberta to ciągła, wypełniająca przestrzeń krzywa fraktalna, wprowadzona przez Davida Hilberta w 1891 roku. W każdej iteracji n krzywa odwiedza dokładnie raz każdą komórkę siatki 2ⁿ × 2ⁿ, a w granicy przechodzi przez każdy punkt jednostkowego kwadratu — nadając jej wymiar fraktalny dokładnie D = 2, równy wymiarowi samej płaszczyzny, mimo że jest pojedynczą ciągłą jednowymiarową ścieżką. Jej najważniejszą właściwością jest zachowanie lokalności: punkty leżące blisko siebie wzdłuż jednowymiarowego indeksu krzywej zwykle odwzorowują się na punkty leżące blisko siebie w przestrzeni, co czyni ją znacznie lepszą od skanowania wierszami lub kolumnami w kontekście dostępu do pamięci przyjaznego dla pamięci podręcznej oraz indeksowania geoprzestrzennego. Ta sama konstrukcja uogólnia się na trzy wymiary, prowadząc pojedynczą ścieżkę przez każdą komórkę sześcianu 2ⁿ × 2ⁿ × 2ⁿ — dokładnie to renderuje ta symulacja w prawdziwym 3D.
Ta symulacja buduje trójwymiarową krzywą Hilberta rzędu od 1 do 5, koloruje ścieżkę według postępu, dzięki czemu można śledzić proces wypełniania przestrzeni, i pozwala swobodnie obracać strukturę. Możesz śledzić rysowanie krzywej lub przewijać jej postęp, aby dokładnie zobaczyć, jak jednowymiarowy porządek odwzorowuje się na trójwymiarową siatkę.
Najczęściej zadawane pytania
Co sprawia, że krzywa Hilberta jest „wypełniająca przestrzeń”?
Krzywa wypełniająca przestrzeń to ciągłe, suriektywne odwzorowanie odcinka na obszar o wyższym wymiarze. Krzywa Hilberta jest granicą ciągu odcinkowo-liniowych przybliżeń; przy każdym rzędzie n krzywa przechodzi przez wszystkie komórki siatki (4ⁿ w 2D, 8ⁿ w 3D), a gdy n dąży do nieskończoności, ścieżka staje się gęsta w sześcianie — każdy punkt jest granicą punktów krzywej. Wbrew intuicji oznacza to, że obiekt 1D może „wypełnić” obszar o wyższym wymiarze bez posiadania objętości, ponieważ „wypełnianie” oznacza tu gęstość, a nie miarę.
Jak krzywa Hilberta zachowuje lokalność?
Dla krzywej Hilberta rzędu n, jeśli dwa indeksy 1D d₁ i d₂ różnią się o 1, ich odpowiadające współrzędne różnią się dokładnie o jedną komórkę. Ściślej: maksymalna odległość przestrzenna między dwoma punktami o indeksach różniących się o co najwyżej k wzdłuż krzywej 1D rośnie znacznie wolniej niż najgorszy przypadek O(k) dla skanowania wierszami. Ta właściwość lokalności jest wykorzystywana w indeksowaniu przestrzennych baz danych, algorytmach niezależnych od pamięci podręcznej (cache-oblivious) procesora oraz w ditheringu obrazów.
Do czego krzywa Hilberta jest wykorzystywana w informatyce?
Głównymi zastosowaniami są indeksowanie przestrzennych baz danych (np. GeoHash wykorzystuje wariant Z-order; PostGIS stosuje porządek Hilberta w indeksach BRIN), operacje macierzowe niezależne od pamięci podręcznej, równoważenie obciążenia w obliczeniach równoległych na siatkach oraz fraktalna kompresja obrazów. Krzywa jest preferowana względem porządku Z (Mortona), ponieważ nie zawiera skoków po przekątnej — każdy krok przechodzi do sąsiedniej komórki — co daje płynniejszą lokalność przestrzenną, zarówno w 2D, jak i w 3D.
Jak konstruuje się trójwymiarową krzywą Hilberta?
Trójwymiarowa krzywa Hilberta rekurencyjnie dzieli sześcian na 8 pod-sześcianów i odwiedza je w porządku kodu Graya, tak aby kolejne pod-sześciany stykały się ścianą. Każdy pod-sześcian jest sam w sobie mniejszą krzywą Hilberta, ale obróconą i odbitą tak, by jego punkt wejścia stykał się z wyjściem poprzedniego pod-sześcianu, a jego wyjście łączyło się z kolejnym. Standardowa implementacja stosuje te obroty na poziomie oktantu rekurencyjnie (lub równoważnie wykorzystuje algorytm transpozycji/kodu Graya Skillinga), aby wygenerować odwzorowanie indeksu na (x, y, z) dla wszystkich 8ⁿ komórek.
Jaka jest różnica między krzywą Hilberta a krzywą Peano?
Obie są krzywymi wypełniającymi przestrzeń, ale dzielą przestrzeń w inny sposób. Krzywa Hilberta dzieli każdy kwadrat na 4 podkwadraty (siatka o podstawie 2) i wykorzystuje ścieżkę w kształcie litery U z dwoma odbiciami przy każdym kroku. Krzywa Peano dzieli na 9 podkwadratów (siatka o podstawie 3) ze skanowaniem w kształcie litery S i była pierwszą opublikowaną krzywą wypełniającą przestrzeń (Giuseppe Peano, 1890 rok — rok przed Hilbertem). Wersja Hilberta jest zwykle preferowana w informatyce, ponieważ siatka o potędze 2 naturalnie pasuje do adresowania binarnego.
Czym jest krzywa Z-order (Mortona) i jak wypada w porównaniu?
Krzywa Z-order, czyli krzywa Mortona, powstaje przez przeplatanie binarnych reprezentacji współrzędnych. Jest niezwykle szybka do obliczenia — wymaga jedynie operacji przeplatania bitów — i jest wykorzystywana w wielu indeksach przestrzennych, w tym w geometrii S2 oraz w niektórych układach tekstur GPU. Ma jednak wadę związaną z lokalnością: wykonuje skoki po przekątnej między ćwiartkami, przez co skupiska bliskich punktów częściej trafiają na odległe indeksy 1D niż w przypadku krzywej Hilberta.
Jaki jest wymiar fraktalny krzywej Hilberta?
Wymiar Hausdorffa (fraktalny) dwuwymiarowej krzywej Hilberta wynosi dokładnie 2; dla trójwymiarowej krzywej Hilberta wynosi dokładnie 3. Oblicza się to z samopodobieństwa: w 3D każdy krok zastępuje jeden odcinek 8 przeskalowanymi kopiami w skali 1/2, więc D = log(8)/log(2) = 3. Wymiar równy wymiarowi przestrzeni osadzenia oznacza, że krzywa jest tak samo „wypełniająca przestrzeń” jak ten obszar, choć wciąż ma zerową objętość w sensie miary Lebesgue'a.
Ile punktów zawiera krzywa 3D przy każdym rzędzie?
Przy rzędzie n trójwymiarowa krzywa Hilberta odwiedza każdą komórkę siatki 2ⁿ × 2ⁿ × 2ⁿ, więc ma 8ⁿ punktów połączonych 8ⁿ − 1 odcinkami. Rząd 1 ma 8 punktów, rząd 2 ma 64, rząd 3 ma 512, rząd 4 ma 4096, a rząd 5 ma 32 768 punktów. Ta symulacja ogranicza rząd do 5, aby liczba wierzchołków i wydajność renderowania pozostały rozsądne w przeglądarce.
Czy krzywa Hilberta jest naprawdę ciągła?
Tak — matematycznie udowodniono, że krzywa Hilberta jest ciągłą funkcją z [0, 1] na kwadrat jednostkowy (lub sześcian w 3D). Dowód wykorzystuje fakt, że każde przybliżenie skończonego rzędu jest jednostajnie ciągłe, a ciąg zbiega jednostajnie, więc funkcja graniczna jest również ciągła na mocy twierdzenia o jednostajnej granicy. Jednak graniczna krzywa nie jest różniczkowalna w żadnym punkcie — nie ma stycznej w żadnym miejscu — co czyni ją przykładem funkcji ciągłej, ale nigdzie nieróżniczkowalnej.
Obserwuj, jak krzywe Hilberta, Peano i Mortona (Z-order) wypełniają płaszczyznę. Koloruj według pozycji na ścieżce, by zobaczyć, jak krzywa Hilberta zachowuje lokalność znacznie lepiej niż Z-order, i zbadaj odwzorowanie 1D↔2D.
3D · Silnik renderujący Three.js/WebGL · cel 60 FPS · działa w całości po stronie klienta, bez instalacji