🌲 Квадрантне дерево

Для рівномірно випадкового набору з n точок в одиничному квадраті запит діапазону, що повертає k точок, у середньому відвідує O(√n + k) вузлів — значно краще, ніж лінійне сканування O(n). У найгіршому випадку (сильно вироджені розподіли точок або запит, що перекриває багато частково включених вузлів) межа зростає до O(n), але на практиці це рідкість. Доданок O(√n) походить від кількості комірок квадрантного дерева, що перетинають межу запиту, не будучи повністю в ній.

У 2D-фізичному рушії перевірка всіх пар об'єктів на колізію коштує O(n²) — нездійсненно для сотень об'єктів. Широкофазний підхід на основі квадрантного дерева вставляє обмежувальний прямокутник кожного об'єкта в дерево, а потім для кожного об'єкта запитує лише об'єкти в тій самій або сусідніх листкових комірках. Якщо об'єкти розподілені по простору, середня кількість кандидатів на об'єкт падає до O(log n) або менше, зменшуючи загальну вартість широкофазного етапу до O(n log n). Такі рушії, як Box2D, Unity 2D і LibGDX, використовують просторові дерева (квадрантні дерева або AABB-дерева) саме для цього.

Точкове квадрантне дерево ділиться в координатах вставленої точки — чотири нащадки представляють квадранти з центром у цій точці. PR (point-region) квадрантне дерево ділить простір у своїй геометричній середній точці незалежно від розташування точок, даючи фіксовану ієрархічну сітчасту структуру. PR-дерева передбачуваніші за глибиною (завжди ⌈log₂(D/ε)⌉ для роздільної здатності ε в домені D) і легші для реалізації без балансування. Цей симулятор використовує варіант PR, оскільки поділ за фіксованою серединою робить візуальну анімацію чистішою.

Максимальна глибина PR-квадрантного дерева обмежена роздільною здатністю системи координат. Для 32-бітних чисел із плаваючою комою в одиничному квадраті мінімальна розрізнювана відстань становить близько 10⁻⁷, тож дерево може досягти щонайбільше ~23 рівнів, перш ніж дві «різні» точки опиняться в одному листку. Для цілочисельних координат у сітці 1024×1024 максимальна глибина дорівнює 10 (оскільки 2¹⁰ = 1024). На практиці дуже глибокі дерева формуються лише тоді, коли багато точок скупчуються на крихітній ділянці; середня глибина для рівномірного набору точок — O(log n).

Так. Вставка проходить від кореня до відповідного листка за O(глибина), розділяючи листок, якщо він перевищує ємність. Видалення прибирає точку, і якщо загальна кількість точок у батьківському вузлі опускається нижче порогу злиття, чотири дочірні вузли згортаються назад у батьківський листок. Обидві операції в середньому займають O(log n) для рівномірно розподілених точок. Часті вставки й видалення в скупченому наборі точок можуть вимагати періодичної перебудови, щоб запобігти сильному дисбалансу.

Октодерево (octree) — це 3D-узагальнення: кожен вузол ділить свій куб на вісім однакових підкубів (октантів). Октодерева широко використовуються в 3D-ігрових рушіях, прискоренні трасування променів та обробці хмар точок LiDAR. Ті самі алгоритмічні принципи застосовуються — запити діапазону, пошук найближчого сусіда та широкофазне виявлення колізій виграють від просторової ієрархії. На практиці 3D-дерева BVH (Bounding Volume Hierarchy) часто перевершують октодерева для динамічних сцен, оскільки адаптуються до розподілу точок, а не використовують фіксовані серединні поділи.

Кодування зображень квадрантним деревом рекурсивно ділить зображення на квадранти. Якщо всі пікселі квадранта потрапляють у межу порогу від одного значення кольору, квадрант зберігається як єдиний листковий вузол із цим кольором — без попіксельного зберігання. Інакше квадрант ділиться знову. Це дає схему стиснення без втрат (при порозі 0) або з втратами (при порозі більше 0). Фрактальне стиснення зображень (яке використовувалося в деяких ранніх іграх на CD-ROM) — споріднена техніка. Сучасні кодеки (HEVC, AV1) використовують подібні до квадрантного дерева ієрархії одиниць кодування (CU) для поділу кадрів на блоки змінного розміру для ентропійного кодування.

Пошук найближчого сусіда починається в корені й спускається в дочірній квадрант, що містить точку запиту, підтримуючи «поточного найкращого» кандидата. При поверненні вгору по рекурсії кожен сусідній квадрант перевіряється: якщо мінімально можлива відстань від запиту до квадранта (відстань до найближчого його кута) менша за поточного найкращого, квадрант потрібно обшукати — інакше він відсікається. На практиці це відвідує O(log n) вузлів для рівномірно випадкових даних, хоча в найгіршому випадку (при зловмисному розташуванні точок) — O(n).

K-d дерево (k-вимірне дерево, Бентлі, 1975) — це бінарне дерево просторового поділу, яке циклічно перемикається між координатними осями для своїх поділів, обираючи медіанну точку вздовж поточної осі як значення поділу. Для 2D-даних k-d дерево чергує x-поділи та y-поділи. На відміну від PR-квадрантного дерева, k-d дерево завжди ідеально збалансоване (глибина O(log n) для n точок), але має гіршу продуктивність кешу і складніше оновлюється динамічно. Емпірично k-d дерева перевершують квадрантні дерева для статичних наборів точок і нижчих вимірностей; квадрантні дерева переважні для динамічних 2D-даних і широкофазного виявлення колізій.

Крива Z-порядку (Мортона) відображає 2D-координати в 1D-індекс шляхом чергування бітів координат x і y: для x = b₁b₂b₃ і y = c₁c₂c₃ код Мортона — b₁c₁b₂c₂b₃c₃. Ця лінеаризація зберігає просторову локальність: точки, близькі на кривій Z-порядку, просторово близькі в 2D. Код Мортона точки точно відповідає шляху від кореня до листка в PR-квадрантному дереві, закодованому як двійковий рядок. Системи баз даних (наприклад, DynamoDB, Google S2) використовують криві Мортона або Гільберта для індексування просторових даних в одновимірних B-деревах, досягаючи продуктивності запитів на рівні квадрантного дерева зі стандартними структурами індексів.

Так — регіональне квадрантне дерево зберігає, які комірки (пікселі) перебувають «усередині» полігона, ділячи їх, доки комірки не стануть повністю всередині, повністю зовні або не досягнуть межі роздільної здатності (тоді вони зберігаються як частково покриті). Векторні квадрантні дерева вставляють відрізки ліній або полігони, перевіряючи кожен рівень поділу на перетин. Наївне зберігання великих полігонів спричиняє дублювання в багатьох вузлах; R-дерева (Гуттман, 1984) зазвичай переважні для індексування прямокутників і полігонів у ГІС, оскільки щільніше обмежують об'єкти й уникають надлишкового багатовузлового зберігання.

Кожна комірка починається як єдиний листок, що утримує всі свої точки. Щойно кількість точок листка перевищує значення повзунка Ємність на листок, він ділиться на чотири рівні дочірні квадранти у власній середині, перерозподіляє свої точки в той дочірній квадрант, до якого вони тепер належать, і стає внутрішнім вузлом. Поділ припиняється, коли глибина комірки перевищує 10, навіть якщо вона все ще утримує більше точок, ніж її ємність.

Низька ємність змушує комірки ділитися набагато швидше, тож дерево росте глибшим із більшою кількістю листків і внутрішніх вузлів для того самого набору точок — це видно в статистиці Листки, Внутрішні вузли та Макс. глибина. Висока ємність дозволяє кожному листку утримувати більше точок перед поділом, створюючи мілкіше дерево, яке відвідує менше вузлів на запит, але сканує більше точок усередині кожного листка.

Перетягування прямокутника в режимі Запит діапазону обходить дерево від кореня, спускаючись лише в ті дочірні квадранти, що перетинають прямокутник, і повністю пропускаючи решту. Статистика Відвідано вузлів точно підраховує, скільки комірок було перевірено таким чином, тоді як Лінійне сканування завжди показує загальну кількість точок — різниця між цими двома числами є заощадженням, яке дерево дає порівняно з перевіркою кожної точки окремо.

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

Кожній точці надається швидкість, і вона відскакує від країв полотна, а на кожному кадрі квадрантне дерево перебудовується й використовується для запуску невеликого запиту діапазону навколо кожної точки, щоб знайти близьких кандидатів на колізію, замість порівняння з кожною іншою точкою. Статистика Результат запиту та Відвідано вузлів показує унікальні кандидатні пари, знайдені деревом, тоді як Лінійне сканування показує загальну кількість пар, яку вимагала б наївна перевірка всіх пар.