Дерево квадрантов

Поделись знанием:
(перенаправлено с «Квадродерево»)
Перейти к: навигация, поиск

Дерево квадрантов (также квадродерево, 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].

Варианты использования

Деревья квадрантов являются двухмерным аналогом деревьев октантов (англ. 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;
  }
}

См. также

Напишите отзыв о статье "Дерево квадрантов"

Ссылки

Примечания

  1. 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
  2. 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].
  3. 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.

Источники

  1. 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.
  2. 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.
  3. [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». [«То то, должно быть, правильно тактическая была война.» (нем.) ] – И, засмеявшись презрительно, прошел в комнату, из которой слышались голоса.
Видно, Пфуль, уже всегда готовый на ироническое раздражение, нынче был особенно возбужден тем, что осмелились без него осматривать его лагерь и судить о нем. Князь Андрей по одному короткому этому свиданию с Пфулем благодаря своим аустерлицким воспоминаниям составил себе ясную характеристику этого человека. Пфуль был один из тех безнадежно, неизменно, до мученичества самоуверенных людей, которыми только бывают немцы, и именно потому, что только немцы бывают самоуверенными на основании отвлеченной идеи – науки, то есть мнимого знания совершенной истины. Француз бывает самоуверен потому, что он почитает себя лично, как умом, так и телом, непреодолимо обворожительным как для мужчин, так и для женщин. Англичанин самоуверен на том основании, что он есть гражданин благоустроеннейшего в мире государства, и потому, как англичанин, знает всегда, что ему делать нужно, и знает, что все, что он делает как англичанин, несомненно хорошо. Итальянец самоуверен потому, что он взволнован и забывает легко и себя и других. Русский самоуверен именно потому, что он ничего не знает и знать не хочет, потому что не верит, чтобы можно было вполне знать что нибудь. Немец самоуверен хуже всех, и тверже всех, и противнее всех, потому что он воображает, что знает истину, науку, которую он сам выдумал, но которая для него есть абсолютная истина. Таков, очевидно, был Пфуль. У него была наука – теория облического движения, выведенная им из истории войн Фридриха Великого, и все, что встречалось ему в новейшей истории войн Фридриха Великого, и все, что встречалось ему в новейшей военной истории, казалось ему бессмыслицей, варварством, безобразным столкновением, в котором с обеих сторон было сделано столько ошибок, что войны эти не могли быть названы войнами: они не подходили под теорию и не могли служить предметом науки.