Розділяй і Володарюй
Наївний пошук перетину точок займає O(N²) часу. З Quadtree це скорочується до
O(N log N).
Як це працює?
- Починаємо з одного великого квадрата.
- Якщо точок > 4 (Capacity), ділимо квадрат на 4 менших.
- Повторюємо рекурсивно.
Застосування:
- Визначення зіткнень в іграх.
- Алгоритм Barnes-Hut для симуляції галактик.
- Стиснення зображень.
Клік: Додати точки
Рух миші: "Query Range" (Зелений квадрат показує зону пошуку).