Krzywa Hilberta i krzywe wypełniające przestrzeń: lokalność i indeksowanie

Parados Peana: linia wypełniająca kwadrat

W 1890 roku Giuseppe Peano stworzył krzywą ciągłą, która przechodzi przez każdą punkt kwadratu dwuwymiarowego. Georg Cantor już dawno pokazał, że linia i kwadrat zawierają taką samą kardynalność punktów, ale Peano poszedł dalej: odpowiedzienna była ciągła, można ją narysować bez podniesienia pióra. Takie krzywe wypełniające przestrzeń są ciągłe, ale sławne za to, że nie są nigdzie różniczkowalne — zmieniają kierunek nieskończenie często na każdym poziomie skali, jak fraktal o wymiarze dokładnie 2 zaszyfrowany jako krzywa jednowymiarowa.

Zasada rekurencyjna Hilberta

David Hilbert w 1891 roku ulepszył konstrukcję Peana do czystszego zasady rekurencyjnej. Współcześnie stosowana prawie na całym świecie jest wersja Hilberta — a nie pierwotna konstrukcja Peana z wykrzyknikami. Zaczynamy od ścieżki U-shape odwiedzającej cztery kwadrante kwadratu. Na kolejnym poziomie, zastępujemy każdy kwadrant mniejszym, obróconym lub odbitym copyem tej samej U-shape, tak aby wyjście jednej podścieżki zgadzało się dokładnie z wejściem nastepnej.

Krzywa stopnia n: 4ⁿ komórek siatki, pełny przebieg na siatkę 2ⁿ × 2ⁿ Kluczowe gwarancje: kolejne indeksy i, i+1 → Zawsze mapują do sąsiednich komórek siatki Obrót na każdym poziomie sprawia, że krzywa jest wyjątkowa: gdziekolwiek ścieżka podkwadratu kończy się, nastepna zaczyna dokładnie obok niej w fizycznym przestrzeni — gwarancja zachowana jest na wszystkich skalach, wszędzie na siatce.

Order n curve: 4ⁿ grid cells, a 2ⁿ × 2ⁿ grid fully traversed

Key guarantee: consecutive indices i, i+1
  → ALWAYS map to spatially adjacent grid cells

Hilbert vs Morton (Z-order)

Prostsza i szybsza alternatywa łączy bity x i y bezpośrednio — krzywa Morton lub Z-order. Podobnie jak w przypadku rekurencyjnej idei kwadrantu, oboje pomijają krok obrotu, co sprawia, że jest znacznie tańsze do obliczenia, ale z utratą lokalności: śledzenie kolejnych indeksów Morton tworzy kształt Z, a każdy przekrój kwadrantu może skoczyć całą sieć, ponieważ bit wyższy może się zmienić, podczas gdy bity niższe zresetują się. Obrót w krzywej Hilberta istnieje exactly to usunąć te skoki, co kosztuje około 2-4 razy więcej obliczeń.

Bazy danych, buforowanie i kompresja

Bazy przestrzenne mapują dwuwymiarowe lub trójwymiarowe współrzędne do pojedynczego indeksu Hilberta i sortują wiersze według tego indeksu w konwencjonalnej strukturze B-tree, zamieniając drobno zapłacone zapytania wielowymiarowe na szybkie skanowanie 1D. Przechodząc po teksturze lub siatce w porządku Hilberta zamiast w kierunku rzędów, zachowuje się małe lokalne sąsiedztwa kontynuum w pamięci, znacząco poprawiając skuteczność buforów CPU i GPU podczas generowania map mipmapów i strumieniowego odczytu. Niektóre algorytmy kompresji obrazu i szumu diteringowego przechodzą po pikselach w porządku Hilberta, ponieważ zachowuje one piksele widziale podobne sąsiednimi w wynikowej 1D strumieniowej. Gier otwartych świata wykorzystują porządek Hilberta lub Morton do utrzymania bloków terenu leżących blisko ze sobą na dysku.

Często zadawane pytania