Крива Гільберта — це неперервна просторово-заповнювальна фрактальна крива, запропонована Давидом Гільбертом у 1891 році. На кожній ітерації n вона обходить кожну клітинку сітки 2ⁿ x 2ⁿ рівно один раз, а в границі проходить через кожну точку одиничного квадрата, тому її фрактальна розмірність дорівнює рівно D = 2. Найважливіша властивість — збереження локальності: точки, близькі вздовж 1D-індексу, здебільшого відображаються в близькі 2D-координати, що робить криву набагато кращою за рядковий обхід у задачах кеш-дружнього доступу до пам'яті та геопросторового індексування.
Симуляція анімує рекурсивну побудову від порядку 1 до 6, забарвлює шлях за прогресом і демонструє збереження локальності у відображенні d ↔ (x, y). Ви також можете порівняти криву Гільберта з кривими Піано і Z-порядку (Мортона).
Що означає «просторово-заповнювальна» крива?
Просторово-заповнювальна крива — це неперервне сюр'єктивне відображення відрізка на 2D-область. Крива Гільберта є границею послідовності кускових апроксимацій: на порядку n вона обходить усі 4ⁿ клітинок, а при n → ∞ стає щільною в квадраті. Це означає, що 1D-об'єкт «заповнює» 2D-область у сенсі щільності, але не у сенсі міри Лебега.
Як крива Гільберта зберігає локальність?
Якщо два індекси d1 і d2 відрізняються на 1, їхні 2D-координати відрізняються рівно на одну клітинку. Загалом максимальна 2D-відстань між точками з індексами, що відрізняються не більше ніж на k, становить O(k^(1/2)) — набагато краще за O(k) у найгіршому випадку для рядкового обходу. Ця властивість використовується у просторових індексах PostGIS і кеш-незалежних матричних алгоритмах.
Де застосовується крива Гільберта у програмуванні?
Основні застосування: просторове індексування баз даних (PostGIS використовує порядок Гільберта в BRIN-індексах), кеш-незалежні матричні операції, балансування навантаження при паралельних обчисленнях на сітках і фрактальне стиснення зображень. Перевага над Z-порядком (Мортоном) полягає у відсутності діагональних стрибків — кожен крок переходить до сусідньої клітинки.
Стандартний алгоритм: починаємо з (x, y) = (0, 0); для кожного рівня від n-1 до 0 витягуємо два біти з d, щоб визначити локальний квадрант, потім повертаємо або відображаємо (x, y) відповідно та додаємо зміщення квадранта. Зворотне відображення (x, y) → d застосовує ту саму логіку у зворотному порядку бітів.
Обидві є просторово-заповнювальними, але по-різному розбивають квадрат. Крива Гільберта ділить кожен квадрат на 4 підквадрати (основа 2) і використовує U-подібний шлях. Крива Піано ділить на 9 підквадратів (основа 3) з S-подібним обходом; вона опублікована першою (Джузеппе Піано, 1890). У програмуванні крива Гільберта зручніша через сітку степенів двійки.
Крива Z-порядку будується чергуванням двійкових представлень x і y: d = ...y1x1y0x0. Її обчислення надзвичайно швидке — лише операції перемежування бітів. Однак у неї є діагональні стрибки між квадрантами, тому близькі 2D-точки частіше потрапляють у далекі 1D-позиції, ніж у кривій Гільберта.
Розмірність Хаусдорфа кривої Гільберта рівно дорівнює 2. Обчислюється із самоподібності: кожен крок замінює один відрізок чотирма копіями з масштабом 1/2, тому D = log(4)/log(2) = 2. Крива «заповнює» 2D-область, хоча її площа за Лебегом залишається нульовою.
На порядку n крива складається з 4ⁿ - 1 відрізків довжиною 1/2ⁿ кожен, тобто повна довжина приблизно дорівнює 2ⁿ. При n = 6 це близько 64 одиниць. Довжина зростає без обмежень, що узгоджується з фрактальною розмірністю 2.
Так — математично доведено, що крива є неперервною функцією з [0, 1] у [0, 1]². Доведення спирається на рівномірну збіжність скінченних апроксимацій. Однак крива не є диференційовною ніде: у жодній точці вона не має дотичної лінії.