Хібертова крива та просторові криві заповнення: Локальність і індексація

Парадокс Піано: лінія, що заповнює квадрат

У 1890 році Джузеппе Піано побудував безперержну криву, яка проходить через усі точки 2D квадрата. Георг Кантор вже показав, що лінія та квадрат містять однакову кардінальність точок, але Піано пішов далі: відповідність могла бути зроблена безперервною, відстежуватися без підняття ручки. Такі криві, що заповнюють простір, є безперервними, але відомо теж, що вони ніде не диференціюються — змінюють напрямок нескінченну кількість разів на кожному масштабі, як фракталь розмірності точно 2, вбраний у форму 1D кривої.

Гілбертова рекурсивна схема

Дідерік Гільберт утотує конструкцію Піано в 1891 році у більш чистий рекурсивний алгоритм, і це версія Гільберта — не початкова зигзагоподібна схема Піано — яка майже завжди використовується сьогодні. Почніть з U-подібної траєкторії, відвідуючи чотири квадранти квадрата. На наступному рівні замініть кожен квадрант меншим, оберненою або відбитою копією тієї ж U-форми, обраної таким чином, щоб вихід однієї підкривої збігався точно з входом наступної.

Крива порядку n: 4ⁿ клітин сітки, повністю простежена 2ⁿ × 2ⁿ сітка Основна гарантія: послідовні індекси i, i+1 → ЗАВЖАЛИЙНО відображаються в сусідні клітини сітки Обертання на кожному рівні робить криву особливою: де б не закінчувався шлях одного підквадрата, наступний бере його поруч у фізичному просторі, а не просто в абстрактному 1D порядку — гарантія, яка зберігається на будь-якому масштабі, всюди на сітці.

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

Гільбертова крива проти Мортона (Z-порядок)

Простіша та швидша альтернатива безпосередньо переплітає біти x і y — це Мортонова або Z-порядок. Вона поділяє ідею рекурсивного квадранту, але пропускає крок повороту, що робить її значно дешевшою у обчисленні з реальною вартістю локальності: відстеження послідовних індексів Мортона створює Z-подібну форму, і кожен перехід через квадрант може зробити різкий стрибок, оскільки висока бітна позиція може перемикнутися, а низькі біти скидаються. Повороти Гільбертової кривої існують конкретно для усунення цих стрибків, приблизно в 2-4 рази дорожче з точки зору обчислень.

Просторові бази даних та їх використання

Просторові бази даних відображають 2D або 3D координати в єдиний білітовий індекс і сортують рядки за ним, використовуючи звичайне дерево B-tree. Це перетворює дорогі багатовимірні запити діапазонів на швидкі 1D сканування. Переміщення текстури або сітки в білітовому порядку замість порядку рядок-за-рядком зберігає сусідні локальні райони в пам'яті, що значно покращує коефіцієнт попадання CPU та GPU для генерації міпмапів і потокового відтворення плиток. Деякі алгоритми стиснення зображень та джитлінгу переміщують пікселі в білітовому порядку саме тому, щоб зберігати візуально подібні пікселі сусідніми в 1D потоці. Відкриті ігри використовують білітові або Мортонівський порядок для підтримки географічно близьких фрагментів рельєфу поруч на диску.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.