Krzywa Peana: Jeden-Dimensionalna Linia Wypełniająca Cały Kwadrat

Krzywa, która złamała przypuszczenie z XIX wieku

W 1890 roku Giuseppe Peano zaskoczył matematyków konstruując krzywą ciągłą przechodzącą przez każdą punkt kwadratu wypełnionego — jednowymiarowy obiekt parametryzowany pojedynczym zmiennej rzeczywistej t, z zakresem pokrywającym prawdziwie dwuwymiarową powierzchnię. Zanim Peano postawił na swoje konstrukcje, większość matematyków przypuszczała, że ciągła krzywa nie może mieć dodatniej powierzchni; wymiar wydawał się jasno invariantem, intuicyjnym celem. Krzywa Peana i znany wersja David Hilberta z 1891 roku pokazały, że jedynie ciągłość pozwala na znacznie dziwniejsze zachowania niż sugerowała intuicja.

Zasada boustrophedonu 3×3

Prawo oryginalne Peana podzieliło kwadrat jednostkowy na siatkę złożoną z dziewięciu mniejszych kwadratów w układzie 3×3 i odwiedza je w porządku boustrophedon ("jak by owca ścinająca się po polach"): od lewej do prawej w dolnej linii, potem z prawej do lewej na środkowej linii, a następnie ponownie od lewej do prawej na górnej linii — tak, aby kolejne mniejsze kwadraty zawsze dzielili wspólną krawędź, zachowując kontynuację ścieżki. Każdy z tych dziewięciu mniejszych kwadratów jest następnie rekurencyjnie podzielony i narysowany w ten sam sposób, alternując orientację boustrophedon (czasem odwrotnie, czasem odbijając), aby końce krzywej subkrywowej zawsze łączyły się gładko ze swoimi sąsiadami po całym rekurencyjnym strukturze.

function peano(x, y, size, level, flip) {
  if (level === 0) { drawTo(x + size/2, y + size/2); return; }
  const s = size / 3;
  const order = flip ? [2,1,0] : [0,1,2];   // boustrophedon row order, alternated
  for (const row of order) {
    const colOrder = (row % 2 === 0) ? [0,1,2] : [2,1,0];
    for (const col of colOrder)
      peano(x + col*s, y + row*s, s, level - 1, !flip);
  }
}

Wypełnianie przestrzeni bez przerwania

Na każdym poziomie rekurencji liczba podkwadratów odwiedzonych wynosi 9^poziom, a przy zwiększaniu poziomu ścieżka krzywej przechodzi niezależnie blisko każdego punktu kwadratu. W matematycznym stronnym granicznym limicie (nieskończona rekurencja), obraz krzywej rzeczywiście równa się całemu wypełnionemu kwadratowi — krzywa o topologicznej wymiarze 1, której zasięg ma miarę Lebesgue'a równą pełnym dwuwymiarowemu obszarem, tzn. zbiór o wymiarze Hausdorffa dokładnie 2. To nie kontradecyje ciągłości krzywej Peana: ciągłość tylko gwarantuje, że wartości parametru t bliskie są mapowane na punkty bliskie, nie że krzywa nie może być wypełniająca przestrzeni; to, że wymiar topologiczny dziedziny (przedział, wymiar 1) różni się od wymiaru zasięgu (cały kwadrat), jest intuicyjnie — i błędnym — założeniem.

Peano vs Hilbert vs Z-order: jaką krzywą wypełniającą powinno się wykorzystać

Krzywa Peana oryginalna używa podziału na siatki o wymiarach 3×3; krzywa Hilberta z 1891 roku używa podziału na siatki o wymiarach 2×2, co stało się znacznie popularniejszym wyborem w informatyce. To dlatego, że właściwość lokalności krzywej Hilberta — punkty blisko siebie w parametryzacji jednowymiarowej pozostają blisko siebie w dwuwymiarowej przestrzeni, a odwrotnie — jest wyraźnie lepsza niż u krzywej Peana lub nawet prostszej krzywej Z-order (Morton), która również podzielona jest na kwadrante, ale w ustalonej kolejności rogu, co powoduje czasami duże skoki między sąsiednimi komórkami. Ta właściwość lokalności jest przyczyną tego, że porządkowanie krzywej Hilberta pojawia się w rzeczywistych systemach: indeksach przestrzennych bazy danych, które chcą, aby zapytania zakresowe dotykały małej liczby stron dyskowych, algorytmach przetwarzania obrazów, które chcą przejrzystego przegladania pikseli, oraz algorytmach diteringu, które chcą, aby rozproszenie błędu pozostawało lokalne w przestrzeni. Krzywa Peana, jako pierwsza historycznie, jest mniej używana w praktyce, ale jest bezpośrednim przodka całą rodzinę krzywych.

Krzywe wypełniające przestrzeń jako sztuczka redukcji wymiarów

Krzywa wypełniająca przestrzeń daje ciągłą (ale nie gładką, a także nie jednoznaczne — punkty mogą być odwiedzane powtarzalnie) surjekcję z przedziału 1D na obszar 2D (lub wymiarów wyższych), co umożliwia rzeczywistą konwersję danych wielowymiarowych w jedno uporządkowane ciąglo. Zachowuje ono znaczącą koncepcję „bliskości”. Ta technika jest wykorzystywana nie tylko w celach purespelenacyjnych: algorytmy równoważności obciążenia, które podziałują domenę symulacji 2D lub 3D między procesory, często korzystają z krzywej Hilberta, aby przypisać ciągłe kawałki długości krzywej do każdego procesora. Gwarantuje to, że obszar przypisany do każdego procesora pozostaje skompaktowany w przestrzeni, co minimalizuje komunikację między procesorami na granicach kawałków.

Uwaga na temat „ wymiaru” samodzielnie

Krzywa Peana jest jednym z powodów, dla których matematycy w końcu potrzebowali wielu bardziej precyzyjnych definicji wymiaru — topologicznego wymiaru (który pozostaje równym 1 dla dowolnej krzywej, czy space-filling czy nie, ponieważ lokalnie nadal wygląda jak linia) przeciwko wymiarowi Hausdorffa lub fraktalowemu (który mierzy, jak zmienia się „wielkość” zbioru podczas powiększania go, i daje krzywej Peana wymiar 2, pasujący do pola, które wypełnia). Taka sama rozróżnienie, zastosowana do zbiorów o wymiarze stricte między liczbami całkowitymi, jest to, co daje fraktalom takim jak koło Sierpinskiego lub krzywa drona granice ich słynne wymiary niecałkowite.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Peano Space-Filling Curve i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.