Дерево квадрантов
Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем и Джоном Бентли в 1974 году. Аналогичное разбиение пространства известно как Q-дерево. Общие черты разных видов деревьев квадрантов:
- разбиение пространства на адаптирующиеся ячейки (англ. adaptable cells),
- максимально возможный объём каждой ячейки,
- соответствие направления дерева пространственному разбиению.
Содержание
Классификация
Деревья квадрантов могут быть классифицированы в соответствии с типом данных, который они представляют — пространством, точками, прямыми, кривыми. Также их можно разделить по тому, зависит ли форма дерева от порядка обработки данных. Некоторые виды деревьев квадрантов:
Region quadtree
Деревья квадрантов, разбивающие пространство (англ. region quadtree), представляют какую-либо часть двумерного пространства разбивая его на 4 квадранта, субквадранты и так далее, причём каждый лист дерева соответствует определённой области. У каждого узла дерева либо 4 потомка, либо их нет вовсе (у листьев). Деревья квадрантов, разбивающие пространство, не являются деревьями в полной мере, поскольку положение субквадрантов не зависит от данных. Более правильное название — префиксные деревья (англ. trie).
Дерево высоты n может быть использовано для представления изображения, состоящего из 2n × 2n пикселей, где каждый пиксель имеет значение 0 или 1. Корень дерева представляет всю область изображения. Если не все пиксели только нули или только единицы, она разбивается. В этом случае каждый лист соответствует множеству пикселей — либо только из нулей, либо только из единиц.
Деревья квадрантов, разбивающие пространство, также могут быть использованы для представления переменного разрешения какого-либо набора данных. Например, информация о температуре может храниться в виде дерева квадрантов, каждый узел которого хранит среднюю температуру дочерних узлов.
Если дерево используется для представления множества точек (например, широты и долготы положений каких-либо городов), области разбиваются до тех пор, пока листья будут содержать не более одной точки.
Point quadtree
Деревья квадрантов, хранящие информацию о точках (англ. point quadtree), — разновидность бинарных деревьев, используемых для хранения информации о точках на плоскости. Форма дерева зависит от порядка задания данных. Использование таких деревьев очень эффективно в сравнении упорядоченных точек плоскости, причём время обработки равно O(log n).
Структура узла
Узел дерева квадрантов, хранящего информацию о точках плоскости, аналогичен узлу бинарного дерева лишь с той оговоркой, что узел первого имеет четыре потомка (по одному на каждый квадрант) вместо двух («правого» и «левого»). Ключ узла состоит из двух компонент (для координат x и y). Таким образом, узел дерева содержит следующую информацию:
- 4 указателя: quad[‘NW’], quad[‘NE’], quad[‘SW’], и quad[‘SE’],
- точка, описываемая следующим образом:
- ключ key, обычно выражает координаты x и y,
- значение value, например, имя.
Edge quadtree
Деревья квадрантов, хранящие информацию о линиях (англ. edge quadtree), используются для описания прямых и кривых. Кривые описываются точными приближениями путём разбиения ячеек на очень мелкие. Это может привести к разбалансировке дерева, что будет означать проблемы с индексацией.
Polygonal map quadtree
Деревья квадрантов, хранящие информацию о многоугольниках (англ. polygonal map quadtree/PMQuadtree), могут содержать информацию о полигонах, в том числе и о вырожденных (имеющих изолированные вершины или грани)[1].
Варианты использования
- Представление изображений.
- Пространственные базы данных.
- Эффективное обнаружение столкновений в двух измерениях.
- Отсечение невидимых частей ландшафта (англ. view frustum culling).
- Хранение данных для табличных или матричных вычислений.
- Вычисления, связанные с многомерными полями (в вычислительной гидродинамике, электромагнетизме).
- Симуляция игры Жизнь[2].
- Вычисление состояний наблюдаемой динамической системы[3].
- Анализ частей фрактальных изображений.
Деревья квадрантов являются двухмерным аналогом деревьев октантов (англ. octree).
Псевдокод
Следующий код демонстрирует использование деревьев квадрантов для хранения информации о точках. Возможны и другие подходы к построению.
Структуры данных
Предполагается использование следующих структур данных.
// Простая структура для представления точки или вектора struct XY { float x; float y; function __construct(float _x, float _y) {...} } // Ограничивающий параллелепипед, выровненный по координатным осям // (axis-aligned bounding box, AABB), половинной размерности с центром struct AABB { XY center; XY halfDimension; function __construct(XY center, XY halfDimension) {...} function containsPoint(XY p) {...} function intersectsAABB(AABB other) {...} }
Класс QuadTree
Класс представляет собственно 4-дерево и корневой узел.
class QuadTree { // Константа — количество элементов, которые можно хранить в одном узле constant int QT_NODE_CAPACITY = 4; // Ограничивающий параллелепипед, выровненный по координатным осям, // показывает границы дерева AABB boundary; // Точки Array of XY [size = QT_NODE_CAPACITY] points; // Потомки QuadTree* northWest; QuadTree* northEast; QuadTree* southWest; QuadTree* southEast; // Методы function __construct(AABB _boundary) {...} function insert(XY p) {...} function subdivide() {...} // Создание 4 потомков, делящих квадрант на 4 равные части function queryRange(AABB range) {...} }
Вставка
Следующий метод осуществляет вставку точки в соответствующий квадрант дерева, осуществляя разбиение, если это необходимо.
class QuadTree { ... // Вставить точку function insert(XY p) { // Игнорировать объекты, не принадлежащие дереву if (!boundary.containsPoint(p)) return false; // Объект не может быть добавлен // Если есть место, осуществить вставку if (points.size < QT_NODE_CAPACITY) { points.append(p); return true; } // Далее необходимо разделить область и добавить точку в какой-либо узел if (northWest == null) subdivide(); if (northWest->insert(p)) return true; if (northEast->insert(p)) return true; if (southWest->insert(p)) return true; if (southEast->insert(p)) return true; // По каким-то причинам вставка может не осуществиться (чего на самом деле не должно происходить) return false; } }
Вхождение в диапазон
Следующий метод находит все точки, входящие в некоторый диапазон.
class QuadTree { ... // Найти точки, входящие в диапазон function queryRange(AABB range) { // Подготовить массив под результат Array of XY pointsInRange; // Отмена, если диапазон не совпадает с квадрантом if (!boundary.insersectsAABB(range)) return pointsInRange; // Пустой список // Проверить объекты текущего уровня for (int p := 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } // Остановка, если больше нет потомков if (northWest == null) return pointsInRange; // Добавить все точки потомков pointsInRange.appendArray(northWest->queryRange(range)); pointsInRange.appendArray(northEast->queryRange(range)); pointsInRange.appendArray(southWest->queryRange(range)); pointsInRange.appendArray(southEast->queryRange(range)); return pointsInRange; } }
См. также
- Двоичное разбиение пространства
- K-мерное дерево
- Октодерево
- R-дерево
- UB-дерево (англ. UB-tree)
- Пространственная база данных
Напишите отзыв о статье "Дерево квадрантов"
Ссылки
Примечания
- ↑ Hanan Samet and Robert Webber. “Storing a Collection of Polygons Using Quadtrees”. ACM Transactions on Graphics July 1985: 182-222. InfoLAB. Web. 23 March 2012
- ↑ Tomas G. Rokicki. [www.ddj.com/hpc-high-performance-computing/184406478 An Algorithm for Compressing Space and Time] (1 апреля 2006). Проверено 20 мая 2009. [www.webcitation.org/6B7n9uxkx Архивировано из первоисточника 3 октября 2012].
- ↑ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.
Источники
- Raphael Finkel and J.L. Bentley (1974). «Quad Trees: A Data Structure for Retrieval on Composite Keys». Acta Informatica 4 (1): 1–9. DOI:10.1007/BF00288933.
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry. — 2nd revised. — Springer-Verlag, 2000. — ISBN 3-540-65620-0. Chapter 14: Quadtrees: pp. 291–306.
- [infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf Storing a Collection of Polygons Using
Quadtrees] (July 1985). Проверено 23 марта 2012. [www.webcitation.org/6B7nAjwgm Архивировано из первоисточника 3 октября 2012].
Внешние ссылки
- [javaprogrammernotes.blogspot.ru/2015/01/why-algorithms-matter-quad-tree-example.html?m=1 Java quad tree example and explanation]
- [www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html A discussion of the Quadtree and an application]
- [homepages.ge.ucl.ac.uk/~mhaklay/java.htm Considerable discussion and demonstrations of Spatial Indexing]
- [digitseven.com/QuadTree.aspx Example C# code for a quad tree]
- [www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ Javascript Implementation of the QuadTree used for collision detection]
- [sourceforge.net/projects/quadtreesim/ C++ Implementation of a QuadTree used for spatial indexing of triangles]
- [bl.ocks.org/mbostock/9078690 Quadtree Search JavaScript implementation]
|
Отрывок, характеризующий Дерево квадрантов
Все люди этой партии ловили рубли, кресты, чины и в этом ловлении следили только за направлением флюгера царской милости, и только что замечали, что флюгер обратился в одну сторону, как все это трутневое население армии начинало дуть в ту же сторону, так что государю тем труднее было повернуть его в другую. Среди неопределенности положения, при угрожающей, серьезной опасности, придававшей всему особенно тревожный характер, среди этого вихря интриг, самолюбий, столкновений различных воззрений и чувств, при разноплеменности всех этих лиц, эта восьмая, самая большая партия людей, нанятых личными интересами, придавала большую запутанность и смутность общему делу. Какой бы ни поднимался вопрос, а уж рой этих трутней, не оттрубив еще над прежней темой, перелетал на новую и своим жужжанием заглушал и затемнял искренние, спорящие голоса.Из всех этих партий, в то самое время, как князь Андрей приехал к армии, собралась еще одна, девятая партия, начинавшая поднимать свой голос. Это была партия людей старых, разумных, государственно опытных и умевших, не разделяя ни одного из противоречащих мнений, отвлеченно посмотреть на все, что делалось при штабе главной квартиры, и обдумать средства к выходу из этой неопределенности, нерешительности, запутанности и слабости.
Люди этой партии говорили и думали, что все дурное происходит преимущественно от присутствия государя с военным двором при армии; что в армию перенесена та неопределенная, условная и колеблющаяся шаткость отношений, которая удобна при дворе, но вредна в армии; что государю нужно царствовать, а не управлять войском; что единственный выход из этого положения есть отъезд государя с его двором из армии; что одно присутствие государя парализует пятьдесят тысяч войска, нужных для обеспечения его личной безопасности; что самый плохой, но независимый главнокомандующий будет лучше самого лучшего, но связанного присутствием и властью государя.
В то самое время как князь Андрей жил без дела при Дриссе, Шишков, государственный секретарь, бывший одним из главных представителей этой партии, написал государю письмо, которое согласились подписать Балашев и Аракчеев. В письме этом, пользуясь данным ему от государя позволением рассуждать об общем ходе дел, он почтительно и под предлогом необходимости для государя воодушевить к войне народ в столице, предлагал государю оставить войско.
Одушевление государем народа и воззвание к нему для защиты отечества – то самое (насколько оно произведено было личным присутствием государя в Москве) одушевление народа, которое было главной причиной торжества России, было представлено государю и принято им как предлог для оставления армии.
Х
Письмо это еще не было подано государю, когда Барклай за обедом передал Болконскому, что государю лично угодно видеть князя Андрея, для того чтобы расспросить его о Турции, и что князь Андрей имеет явиться в квартиру Бенигсена в шесть часов вечера.
В этот же день в квартире государя было получено известие о новом движении Наполеона, могущем быть опасным для армии, – известие, впоследствии оказавшееся несправедливым. И в это же утро полковник Мишо, объезжая с государем дрисские укрепления, доказывал государю, что укрепленный лагерь этот, устроенный Пфулем и считавшийся до сих пор chef d'?uvr'ом тактики, долженствующим погубить Наполеона, – что лагерь этот есть бессмыслица и погибель русской армии.
Князь Андрей приехал в квартиру генерала Бенигсена, занимавшего небольшой помещичий дом на самом берегу реки. Ни Бенигсена, ни государя не было там, но Чернышев, флигель адъютант государя, принял Болконского и объявил ему, что государь поехал с генералом Бенигсеном и с маркизом Паулучи другой раз в нынешний день для объезда укреплений Дрисского лагеря, в удобности которого начинали сильно сомневаться.
Чернышев сидел с книгой французского романа у окна первой комнаты. Комната эта, вероятно, была прежде залой; в ней еще стоял орган, на который навалены были какие то ковры, и в одном углу стояла складная кровать адъютанта Бенигсена. Этот адъютант был тут. Он, видно, замученный пирушкой или делом, сидел на свернутой постеле и дремал. Из залы вели две двери: одна прямо в бывшую гостиную, другая направо в кабинет. Из первой двери слышались голоса разговаривающих по немецки и изредка по французски. Там, в бывшей гостиной, были собраны, по желанию государя, не военный совет (государь любил неопределенность), но некоторые лица, которых мнение о предстоящих затруднениях он желал знать. Это не был военный совет, но как бы совет избранных для уяснения некоторых вопросов лично для государя. На этот полусовет были приглашены: шведский генерал Армфельд, генерал адъютант Вольцоген, Винцингероде, которого Наполеон называл беглым французским подданным, Мишо, Толь, вовсе не военный человек – граф Штейн и, наконец, сам Пфуль, который, как слышал князь Андрей, был la cheville ouvriere [основою] всего дела. Князь Андрей имел случай хорошо рассмотреть его, так как Пфуль вскоре после него приехал и прошел в гостиную, остановившись на минуту поговорить с Чернышевым.
Пфуль с первого взгляда, в своем русском генеральском дурно сшитом мундире, который нескладно, как на наряженном, сидел на нем, показался князю Андрею как будто знакомым, хотя он никогда не видал его. В нем был и Вейротер, и Мак, и Шмидт, и много других немецких теоретиков генералов, которых князю Андрею удалось видеть в 1805 м году; но он был типичнее всех их. Такого немца теоретика, соединявшего в себе все, что было в тех немцах, еще никогда не видал князь Андрей.
Пфуль был невысок ростом, очень худ, но ширококост, грубого, здорового сложения, с широким тазом и костлявыми лопатками. Лицо у него было очень морщинисто, с глубоко вставленными глазами. Волоса его спереди у висков, очевидно, торопливо были приглажены щеткой, сзади наивно торчали кисточками. Он, беспокойно и сердито оглядываясь, вошел в комнату, как будто он всего боялся в большой комнате, куда он вошел. Он, неловким движением придерживая шпагу, обратился к Чернышеву, спрашивая по немецки, где государь. Ему, видно, как можно скорее хотелось пройти комнаты, окончить поклоны и приветствия и сесть за дело перед картой, где он чувствовал себя на месте. Он поспешно кивал головой на слова Чернышева и иронически улыбался, слушая его слова о том, что государь осматривает укрепления, которые он, сам Пфуль, заложил по своей теории. Он что то басисто и круто, как говорят самоуверенные немцы, проворчал про себя: Dummkopf… или: zu Grunde die ganze Geschichte… или: s'wird was gescheites d'raus werden… [глупости… к черту все дело… (нем.) ] Князь Андрей не расслышал и хотел пройти, но Чернышев познакомил князя Андрея с Пфулем, заметив, что князь Андрей приехал из Турции, где так счастливо кончена война. Пфуль чуть взглянул не столько на князя Андрея, сколько через него, и проговорил смеясь: «Da muss ein schoner taktischcr Krieg gewesen sein». [«То то, должно быть, правильно тактическая была война.» (нем.) ] – И, засмеявшись презрительно, прошел в комнату, из которой слышались голоса.
Видно, Пфуль, уже всегда готовый на ироническое раздражение, нынче был особенно возбужден тем, что осмелились без него осматривать его лагерь и судить о нем. Князь Андрей по одному короткому этому свиданию с Пфулем благодаря своим аустерлицким воспоминаниям составил себе ясную характеристику этого человека. Пфуль был один из тех безнадежно, неизменно, до мученичества самоуверенных людей, которыми только бывают немцы, и именно потому, что только немцы бывают самоуверенными на основании отвлеченной идеи – науки, то есть мнимого знания совершенной истины. Француз бывает самоуверен потому, что он почитает себя лично, как умом, так и телом, непреодолимо обворожительным как для мужчин, так и для женщин. Англичанин самоуверен на том основании, что он есть гражданин благоустроеннейшего в мире государства, и потому, как англичанин, знает всегда, что ему делать нужно, и знает, что все, что он делает как англичанин, несомненно хорошо. Итальянец самоуверен потому, что он взволнован и забывает легко и себя и других. Русский самоуверен именно потому, что он ничего не знает и знать не хочет, потому что не верит, чтобы можно было вполне знать что нибудь. Немец самоуверен хуже всех, и тверже всех, и противнее всех, потому что он воображает, что знает истину, науку, которую он сам выдумал, но которая для него есть абсолютная истина. Таков, очевидно, был Пфуль. У него была наука – теория облического движения, выведенная им из истории войн Фридриха Великого, и все, что встречалось ему в новейшей истории войн Фридриха Великого, и все, что встречалось ему в новейшей военной истории, казалось ему бессмыслицей, варварством, безобразным столкновением, в котором с обеих сторон было сделано столько ошибок, что войны эти не могли быть названы войнами: они не подходили под теорию и не могли служить предметом науки.