Квадтри дерево: Як шукати на площині без перегляду кожної точки

Проблема з плоским списком точок

Запитайте "Які з цих тисячі точок лежать всередині цього невеликого прямокутника?" і простий масив змушує перевіряти кожен окремий пункт — O(n) на запит, незалежно від того, наскільки невеликий прямокутник або скільки порожнього простору випадково трапляється в решті площини. Квадрічна структура, яку представили Рафаель Фінкель та Дж. Л. Бентли у 1974 році, вирішує цю проблему, організовуючи простір сам по собі, а не тільки точки в ньому, щоб цілі порожні регіони можна було пропустити без необхідності їх відвідування.

Розділення на чотири частини, коли вузол переповнюється

Кінець тетрадру охоплює квадратну область у площині та містить точки до певної невеликої ємності, зазвичай від 4 до 16. Як тільки вузол перевищував би цю ємність, він ділився на рівно чотири рівних дітей — ПЗ, ПС, ОТ, ЗТ — і його точки перерозподілялися між ними відповідно до того, в якому квадранті вони потрапляють. Назва походить безпосередньо від цього чотирьохстороннього поділу; аналогічна структура у трьох вимірах, розділення куба на вісім дітей, є октом.

insert(вузол, точка): якщо вузол не має дочірніх вузлів і довжина вузла.точок < ємність: додати точку в вузол.точки; повертати якщо вузол не має дочірніх вузлів: розділити(вузол) // створити ПЗ, ПС, ОТ, ЗТ, перерозподілити insert(дочірній вузол, що містить точку, точку) Дерево стає глибоким там, де точки щільні, і неглибоким там, де вони рідкісні — воно автоматично адаптується до даних, на відміну від фіксованої сітки, яка витрачає пам’ять на порожні клітини або переповнює занадто багато точок в одному контейнері, де б дані не скупчилися.

insert(node, point):
    if node has no children and node.points.length < capacity:
        node.points.push(point); return
    if node has no children:
        subdivide(node)          // create NW, NE, SW, SE, redistribute
    insert(child that contains point, point)

Чому запит на діапазон пропускає більшість дерева

Щоб знайти кожну точку всередині заданого прямокутника запиту, потрібно пройтися деревом від кореня і в кожному вузлі порівнювати квадрат вузла з прямокутником запиту на перетином: якщо два не перетинаються зовсім, весь піддерево відкидається в одному порівнянні, незалежно від того скільки точок воно містить. Якщо квадрат вузла повністю знаходиться всередині запиту, кожна точка нижче нього збирається без додаткових перевірок. Тільки вузли, які частково перетинаються з запитом, потрібно рекурсивно проходити в їхніх дітей.

query(node, rect, out): if !intersects(node.bounds, rect): return // видаляємо все піддерево for p in node.points: if rect.contains(p): out.push(p) if node has children: for child in [NW, NE, SW, SE]: query(child, rect, out)

query(node, rect, out):
    if !intersects(node.bounds, rect): return          // prune the whole subtree
    for p in node.points: if rect.contains(p): out.push(p)
    if node has children:
        for child in [NW, NE, SW, SE]: query(child, rect, out)

Де куди справді принесуть корисність квадтриї

Ігрові та фізичні рушії використовують квадтриї для широковільних виявлень зіткнень: замість перевірки кожного пари з n рухомих об'єктів один проти одного (O(n²)), кожен об’єкт потрібно лише перевірити проти кількох інших об’єктів, які діляться з ним одним вузлом або сусіднім вузлом. Алгоритм Barnes-Hut будує нову квадтрию кожного етапу симуляції для наближення довгодальніх гравітаційних чи електростатичних сил у O(n log n). Сервери карт та зображень використовують квадтрию індексів плиток, щоб вирішити, який квадрат зображення потрібно отримати на певному рівні масштабування, а географічні бази даних використовують її для відповіді на запитання «що поруч» над мільйонами записів без повного сканування таблиць.

Торгування: побудова проти оновлення

Квадтри може бути дешево побудовано — O(n log n) для введення n точок по одній за раз — але підтримка одного правильного, коли точки рухаються, де відрізняються реалізації. Видалення та повторний ввід рухомої точки кожного кадру є простим і часто швидким; більш ретельна реалізація об'єднує дітей вузла назад разом, коли сумарна кількість точок їхнього об’єднання падає нижче за межі здатності, щоб дерево не залишалося надмірно глибоким після розсіювання об’єктів. Для робочого навантаження, яке домінує в рухомих точках, а не в рухливих запитах, деякі двигуни просто будують все дерево заново з нуля кожного кадру — O(n log n) на перебудову часто дешевше, ніж бухгалтерський облік, необхідний для інкрементних оновлень.

Frequently asked questions

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

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