QuadTree для самых маленьких

Текст полностью переписан, чтобы стать лучше :-)

Я сделал свою реализацию quadtree и желаю поделиться ей с народом. Оказалось, что это простая штука, которую несложно сделать.

Демка: Посмотреть.
Исходники (на AS3): скачать.
(Обновлено 28/01/2011 — поправлены баги, улучшена демка)

Зачем вообще это нужно?
Quadtree — это структура данных позволяющая ответить на вопросы: какие из кучи прямоугольных объектов пересекаются с заданным прямоугольником, и какие из кучи прямоугольных объектов пересекаются между собой.

На эти вопросы можно ответить и без quadtree, но скорее всего это выйдет дольше:
1. Если просто перебирать все объекты — это выйдет очень долго. Хотя часто этот подход срабатывает :-)
2. Если сделать сетку, и поместить ссылку на каждый объект в те ячейки, которые он пересекает, то во-первых вы быстро выясните, что это не так легко и быстро, если объект больше ячейки сетки, а во-вторых вы например будете напрасно перебирать клетки сетки, в которых ничего нет, а для тех, в которых окажется много объектов, вы будете очень долго искать пересечения. Это очень популярная техника, подкупающая простотой идеи, и действительно простая и эффективная, в случае если объекты меньше размера ячейки сетки и равномерно распределены в пространстве.

Как это работает?
Quadtree концептуально немного сложнее сетки, но в реализации даже проще, чем сетка, учитывающая, что объекты могут быть больше размера ячейки.

Основной идеей Quadtree является последовательное разделение участков пространства на четыре части. Т.е. берем квадрат, делим его на четыре квадрата поменьше, каждый получившийся — еще на четыре, и так далее. Получается квадратное дерево, потому так и называется.

Основным объектом нашего Quadtree является как раз такой квадрат, или узел дерева. Он содержит список тех объектов, которые находятся непосредственно в нем, а также ссылки на четыре дочерних квадрата поменьше.

Чтобы поместить прямоугольник в Quadtree мы находим среди всех наших квадратов такой, который
а) содержит наш прямоугольник целиком (это основное и обязательное требование)
б) содержит как можно меньше других прямоугольников

Каждый объект добавляется только в один узел дерева, т.е. если он содержится в каком-то квадрате, то он уже не добавляется в родителя этого квадрата, хотя физически (на плоскости) он и в нем содержится тоже.

Алгоритм добавления очень простой:
1) Начинаем с самого большого квадрата.
2) Если в дочерних квадратах пусто, и в самом квадрате пусто, то добавляем в этот текущий квадрат
3) Если объект не вписывается целиком ни в один из дочерних квадратов, то также добавляем объект в текущий квадрат
4) Если объект все же вписывается целиком в один из дочерних квадратов, то переходим к пункту (2), но уже с этим квадратом

Возможно имеет смысл ввести ограничение на минимальный размер квадрата (и соответственно глубину дерева) — но реально этот параметр сам собой ограничится размерами объектов и плотностью их распределения в пространстве.

Что если объект не содержится в самом большом квадрате? Три варианта:
1) Выдать ошибку.
2) Сделать квадрат побольше, добавив имеющийся самый большой в него в качестве дочернего.
3) Сделать как я :-) Смотри демку и исходники. Я на этот вопрос забил, но при реализации он решился сам собой, хоть и неэффективно для объектов вне квадрата.

Как использовать полученное дерево после добавления всех объектов?
Чтобы найти пересекающиеся с заданным прямоугольником объекты делаем так:
1) Начинаем с самого большого квадрата.
2) Проверяем все объекты из списка текущего квадрата на пересечение с прямоугольником.
3) Проверяем все четыре дочерних квадрата на пересечение с прямоугольником и для пересекающихся переходим к пункту 2

Чтобы найти все пересекающие многоугольники думаем сами, т.к. я пока не делал и врать не буду, но это не сильно сложно сделать: просто иерархически все перебрать, проверив на пересечение только потенциально пересекающиеся объекты.

Что делать если объект передвинулся?
Я не нашел ничего лучше, чем вынуть его из Quadtree и засунуть обратно. Скорее всего это можно оптимизировать, хотя бы проверив что он остается в том же квадрате и не трогать его тогда, но на практике в моем случае такая оптимизация ничего не дала. Наверное можно что-то еще придумать. Могу порекомендовать поменьше объекты двигать :-)

Еще посмотреть:
github.com/AdamAtomic/flixel/blob/master/org/flixel/FlxQuadTree.as — Исходник из фликселя (ссылка дана Eugene)
www.kyleschouviller.com/wsuxna/quadtree-source-included/ — на английском, но с картинками. Еще там есть исходники на C#, но не смотрел их, а текст хороший.