Quadtree

Эта статья имеет нечеткий стиль цитирования . Используемые ссылки можно сделать более ясными с помощью другого или последовательного стиля цитирования и сносок . ( Апрель 2015 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Квадродерево точечной области с точечными данными. Вместимость ковша 1.

Пошаговое сжатие изображения Quadtree. Слева показано сжатое изображение с ограничивающими рамками дерева, а справа показано только сжатое изображение.

Дерева квадрантов является структура данных , дерево , в котором каждый внутренний узел имеет ровно четыре детей. Квадродеревья являются двумерным аналогом октодеревьев и чаще всего используются для разделения двумерного пространства путем рекурсивного деления его на четыре квадранта или области. Данные, связанные с листовой ячейкой, различаются в зависимости от приложения, но листовая ячейка представляет собой «единицу интересной пространственной информации».

Разделенные области могут быть квадратными или прямоугольными или могут иметь произвольную форму. Эта структура данных была названа квадродеревом Рафаэлем Финкелем и Дж. Л. Бентли в 1974 году. ^[1] Подобное разбиение также известно как Q-дерево . Все формы квадродеревьев имеют некоторые общие черты:

• Они разлагают пространство на адаптируемые ячейки
• Каждая ячейка (или ведро) имеет максимальную вместимость. Когда достигается максимальная вместимость, ковш разделяется.
• Каталог дерева следует за пространственной декомпозицией дерева квадрантов.

Дерево-пирамида ( Т-пирамида ) является «полным» деревом; каждый узел Т-пирамиды имеет четыре дочерних узла, кроме листовых; все листья находятся на одном уровне, уровне, соответствующем отдельным пикселям изображения. Данные в древовидной пирамиде могут компактно храниться в массиве как неявная структура данных, аналогично тому, как полное двоичное дерево может компактно храниться в массиве . ^[2]

Типы [ править ]

Кваддеревья можно классифицировать по типу данных, которые они представляют, включая области, точки, линии и кривые. Дерева квадратов также можно классифицировать по тому, является ли форма дерева независимой от порядка обработки данных. Ниже приведены распространенные типы квадродеревьев.

Область квадродерева [ править ]

Квадратное дерево региона представляет собой разделение пространства в двух измерениях путем разложения региона на четыре равных квадранта, субквадранта и так далее, при этом каждый конечный узел содержит данные, соответствующие определенной подобласти. Каждый узел в дереве либо имеет ровно четыре дочерних элемента, либо не имеет потомков (листовой узел). Высота квадродеревьев, которые следуют этой стратегии декомпозиции (т. Е. Подразделение субквадрантов до тех пор, пока в субквадранте есть интересные данные, для которых требуется большее уточнение), чувствительна и зависит от пространственного распределения интересных областей в разбиваемом пространстве. Область квадранты представляют собой тип синтаксического дерева .

Квадродерево области с глубиной n может использоваться для представления изображения, состоящего из 2 ⁿ × 2 ⁿпикселей, где значение каждого пикселя равно 0 или 1. Корневой узел представляет всю область изображения. Если пиксели в какой-либо области не полностью равны нулю или единице, она разделяется. В этом приложении каждый листовой узел представляет собой блок пикселей, состоящий только из нулей или единиц. Обратите внимание на потенциальную экономию места, когда эти деревья используются для хранения изображений; изображения часто имеют много областей значительного размера, которые имеют одинаковое значение цвета повсюду. Вместо того, чтобы хранить большой двумерный массив каждого пикселя изображения, дерево квадратов может захватывать ту же информацию, потенциально на много разделительных уровней выше, чем ячейки размером с пиксельное разрешение, которые нам в противном случае потребовались бы. Разрешение дерева и общий размер ограничены размерами пикселей и изображений.

Квадродерево области также может использоваться как представление поля данных с переменным разрешением. Например, температуры в области могут храниться в виде квадродерева, где каждый листовой узел хранит среднюю температуру по подобласти, которую он представляет.

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

Точечное дерево квадрантов [ править ]

Точечное квадродерево ^[3] представляет собой адаптацию двоичного дерева, используемого для представления двумерных точечных данных. Оно разделяет черты всех квадродеревьев, но является настоящим деревом, поскольку центр подразделения всегда находится в точке. Он часто очень эффективен при сравнении двумерных упорядоченных точек данных, обычно работающих за время O (log n) . Для полноты картины стоит упомянуть точечные квадродеревья, но деревья k -d превзошли их как инструменты для обобщенного двоичного поиска. ^[4]

Точечные квадродеревья строятся следующим образом. Учитывая следующую точку для вставки, мы находим ячейку, в которой она находится, и добавляем ее в дерево. Новая точка добавляется таким образом, что содержащая ее ячейка делится на квадранты вертикальными и горизонтальными линиями, проходящими через точку. Следовательно, клетки бывают прямоугольными, но не обязательно квадратными. В этих деревьях каждый узел содержит одну из входных точек.

Поскольку разделение плоскости определяется порядком вставки точки, высота дерева чувствительна к порядку вставки и зависит от него. Вставка в «плохом» порядке может привести к дереву с высотой, линейной по количеству входных точек (после чего оно становится связанным списком). Если набор точек статический, можно выполнить предварительную обработку для создания дерева сбалансированной высоты.

Структура узла для точечного квадродерева [ править ]

Узел точечного квадродерева похож на узел двоичного дерева , с основным отличием в том, что он имеет четыре указателя (по одному для каждого квадранта) вместо двух («левый» и «правый»), как в обычном двоичном дереве. . Также ключ обычно разбивается на две части, относящиеся к координатам x и y. Следовательно, узел содержит следующую информацию:

• четыре указателя: quad ['NW'], quad ['NE'], quad ['SW'] и quad ['SE']
• точка; который, в свою очередь, содержит:
  • ключ; обычно выражается как координаты x, y
  • ценить; например имя

Квадродерево точечной области (PR) [ править ]

Квадродеревья точечных областей (PR) ^{[5] [6]} очень похожи на квадродеревья областей. Разница в типе информации, хранящейся о ячейках. В квадродереве области хранится единообразное значение, которое применяется ко всей площади ячейки листа. Однако ячейки квадродерева PR хранят список точек, которые существуют в ячейке листа. Как упоминалось ранее, для деревьев, следующих этой стратегии декомпозиции, высота зависит от пространственного распределения точек. Подобно точечному квадродереву, квадродерево PR может также иметь линейную высоту, если задан «плохой» набор.

Edge quadtree [ править ]

Квадродеревья ребер ^{[7] [8]} (во многом как квадродеревья PM) используются для хранения линий, а не точек. Кривые аппроксимируются путем деления ячеек на части с очень высоким разрешением, в частности, до тех пор, пока на ячейку не будет одного сегмента линии. Близкие к углам / вершинам квадродеревья ребер будут продолжать делиться до тех пор, пока не достигнут максимального уровня разложения. Это может привести к чрезвычайно несбалансированным деревьям, которые могут нарушить цель индексации.

Полигональная карта (PM) quadtree [ править ]

Квадродерево полигональной карты (или PM Quadtree) - это разновидность квадродерева, которая используется для хранения наборов многоугольников, которые могут быть вырожденными (то есть, они имеют изолированные вершины или ребра). ^{[9] [10]} Большое различие между квадродеревьями PM и квадродеревьями ребер состоит в том, что рассматриваемая ячейка не разделяется, если сегменты встречаются в вершине в ячейке.

Существует три основных класса квадродеревьев PM, которые различаются в зависимости от того, какую информацию они хранят в каждом черном узле. Квадродеревья PM3 могут хранить любое количество непересекающихся ребер и не более одной точки. Кваддеревья PM2 такие же, как и квадродеревья PM3, за исключением того, что все ребра должны иметь одну и ту же конечную точку. Наконец, квадродеревья PM1 похожи на PM2, но черные узлы могут содержать точку и ее ребра или просто набор ребер, которые имеют общую точку, но у вас не может быть точки и набора ребер, которые не содержат точку.

Сжатые квадродерева [ править ]

В этом разделе суммируется подраздел из книги Сариэль Хар-Пелед . ^[11]

Если бы мы сохранили каждый узел, соответствующий разделенной ячейке, мы могли бы сохранить много пустых узлов. Мы можем сократить размер таких разреженных деревьев, сохраняя только поддеревья, листья которых содержат интересные данные (то есть «важные поддеревья»). На самом деле мы можем еще больше сократить размер. Когда мы сохраняем только важные поддеревья, процесс отсечения может оставлять длинные пути в дереве, где промежуточные узлы имеют степень два (ссылка на один родительский и один дочерний). Оказывается, нам нужно только сохранить узел в начале этого пути (и связать с ним некоторые метаданные для представления удаленных узлов) и присоединить поддерево с корнем на его конце к . Эти сжатые деревья все еще могут иметь линейную высоту при заданных «плохих» входных точках.${\displaystyle u}$${\displaystyle u}$

Несмотря на то, что мы обрезаем большую часть дерева при выполнении этого сжатия, все же возможно выполнить поиск, вставку и удаление в логарифмическом времени, используя кривые Z- порядка . Z -порядок кривой отображает каждую ячейку полного дерева квадрантов (и , следовательно , даже сжатого квадрадерево) в момент к одномерной линии (и отображает его обратно в время тоже), создавая общий порядок на элементах. Следовательно, мы можем хранить квадродерево в структуре данных для упорядоченных наборов (в которой мы храним узлы дерева). Прежде чем продолжить, мы должны сформулировать разумное предположение: мы предполагаем, что, имея два действительных числа, выраженных в двоичном формате, мы можем вычислить в${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle \alpha ,\beta \in [0,1)}$${\displaystyle O(1)}$time - индекс первого бита, которым они различаются. Мы также предполагаем, что можем вычислить во времени наименьшего общего предка двух точек / ячеек в дереве квадрантов и установить их относительный Z- порядок, и мы можем вычислить функцию пола во времени. С этими предположениями, определение местоположения данной точки (то есть определение ячейки, которая будет содержать ), операции вставки и удаления могут выполняться во времени (то есть время, необходимое для выполнения поиска в базовой структуре данных упорядоченного набора).${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle q}$${\displaystyle q}$${\displaystyle O(\log {n})}$

Чтобы определить местоположение точки (т.е. найти ее ячейку в сжатом дереве):${\displaystyle q}$

1. Найти существующую ячейку в сжатом дереве , которое приходит , прежде чем в Z -порядке. Позвоните в эту ячейку .${\displaystyle q}$${\displaystyle v}$
2. Если , вернись .${\displaystyle q\in v}$${\displaystyle v}$
3. В противном случае найдите то, что было бы наименьшим общим предком точки и ячейки в несжатом дереве квадрантов. Назовите эту предков клеткой .${\displaystyle q}$${\displaystyle v}$${\displaystyle u}$
4. Найти существующую ячейку в сжатом дереве , которое приходит , прежде чем в Z -порядок и вернуть его.${\displaystyle u}$

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

Некоторые распространенные использования квадродеревьев [ править ]

• Представление изображения
  
• Обработка изображений
• Генерация сетки
• Пространственная индексация , запросы местоположения точки и запросы диапазона
• Эффективное обнаружение столкновений в двух измерениях
• Просмотр усеченной границы данных о местности
• Хранение разреженных данных, таких как информация о форматировании для электронной таблицы ^[12] или для некоторых матричных вычислений ^{[ необходима ссылка ]}
• Решение многомерных полей ( вычислительная гидродинамика , электромагнетизм )
• Программа моделирования «Игра жизни» Конвея . ^[13]
• Оценка состояния ^[14]
• Кваддеревья также используются в области анализа фрактальных изображений.
• Максимальные непересекающиеся множества

Обработка изображений с использованием квадродеревьев [ править ]

Quadtrees, в частности, область квадрантов , одолжил себя хорошо для приложений обработки изображений. Мы ограничим наше обсуждение данными двоичного изображения, хотя квадродеревья областей и выполняемые над ними операции обработки изображений также подходят для цветных изображений. ^{[4] [15]}

Image Union / Intersection [ править ]

Одним из преимуществ использования квадродеревьев для обработки изображений является то, что заданные операции объединения и пересечения можно выполнять просто и быстро. ^{[4] [16] [17] [18] [19]} Для двух двоичных изображений объединение изображений (также называемое наложением ) создает изображение, в котором пиксель является черным, если любое из входных изображений имеет черный пиксель в том же месте. . То есть пиксель в выходном изображении будет белым только тогда, когда соответствующий пиксель в обоихвходные изображения белые, иначе выходной пиксель черный. Вместо того, чтобы выполнять операцию пиксель за пикселем, мы можем вычислить объединение более эффективно, используя способность квадродерева представлять несколько пикселей с помощью одного узла. В целях обсуждения ниже, если поддерево содержит как черные, так и белые пиксели, мы будем говорить, что корень этого поддерева окрашен в серый цвет.

Алгоритм работает путем обхода двух входных квадродеревьев ( и ) при построении выходного квадродерева . Неформально алгоритм выглядит следующим образом. Рассмотрим узлы и соответствующие одной и той же области на изображениях.${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle T}$${\displaystyle v_{1}\in T_{1}}$${\displaystyle v_{2}\in T_{2}}$

• Если или черный, соответствующий узел создается в черном цвете. Если только один из них черный, а другой серый, серый узел будет содержать поддерево внизу. Это поддерево проходить не нужно.${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle T}$
• Если (соответственно ) белый, (соответственно ) и поддерево под ним (если есть) копируется в .${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle T}$
• Если оба и серые, то учитываются соответствующие дочерние элементы и .${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle v_{2}}$

Хотя этот алгоритм работает, он сам по себе не гарантирует минимального размера квадродерева. Например, рассмотрим результат, если бы мы объединили шахматную доску (где каждая плитка - пиксель) размера с ее дополнением. Результатом является гигантский черный квадрат, который должен быть представлен деревом квадратов только с корневым узлом (окрашенным в черный цвет), но вместо этого алгоритм создает полное 4-арное дерево глубины . Чтобы исправить это, мы выполняем обход получившегося квадродерева снизу вверх, где проверяем, имеют ли четыре дочерних узла одинаковый цвет, и в этом случае мы заменяем их родительский лист листом того же цвета. ^[4]${\displaystyle 2^{k}\times 2^{k}}$${\displaystyle k}$

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

Маркировка подключенных компонентов [ править ]

Рассмотрим два соседних черных пикселя в двоичном изображении. Они являются смежными, если имеют общий ограничивающий горизонтальный или вертикальный край. Как правило, два черных пикселя соединяются, если до одного можно добраться от другого, перемещаясь только к соседним пикселям (т. Е. Между ними есть путь черных пикселей, где каждая последующая пара является смежной). Каждый максимальный набор связанных черных пикселей является связным компонентом . Используя представление изображений в виде дерева квадрантов, Самет ^[20] показал, как мы можем найти и пометить эти связанные компоненты во времени, пропорциональном размеру дерева квадрантов. ^{[4] [21]} Этот алгоритм также можно использовать для раскраски многоугольников.

Алгоритм работает в три этапа:

• установить отношения смежности между черными пикселями
• обработать отношения эквивалентности из первого шага, чтобы получить одну уникальную метку для каждого связного компонента
• пометьте черные пиксели меткой, связанной с их подключенным компонентом

Чтобы упростить обсуждение, предположим, что дочерние элементы узла в дереве квадрантов следуют Z- порядку (SW, NW, SE, NE). Поскольку мы можем рассчитывать на эту структуру, для любой ячейки мы знаем, как перемещаться по дереву квадрантов, чтобы найти соседние ячейки на разных уровнях иерархии.

Шаг первый выполняется с обходом квадродерева после заказа . Для каждого черного листа мы смотрим на узел или узлы, представляющие ячейки, которые являются северными соседями и восточными соседями (т.е. северные и восточные ячейки, которые имеют общие края с ячейкой ). Поскольку дерево организовано в Z- порядке, у нас есть инвариант, о котором южные и западные соседи уже учтены и учтены. Пусть сейчас рассматривается северный или восточный сосед . Если представляет черные пиксели:${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$

• Если только одна из или имеет метку, назначьте эту метку другой ячейке${\displaystyle u}$${\displaystyle v}$
• Если ни у одного из них нет ярлыков, создайте один и назначьте его им обоим.
• Если и имеют разные метки, запишите эквивалентность этих меток и двигайтесь дальше${\displaystyle u}$${\displaystyle v}$

Второй шаг можно выполнить с помощью структуры данных union-find . ^[22] Мы начинаем с каждой уникальной метки как отдельного набора. Для каждого отношения эквивалентности, отмеченного на первом шаге, мы объединяем соответствующие множества. Впоследствии каждый отдельный оставшийся набор будет связан с отдельным компонентом связности на изображении.

На третьем этапе выполняется еще один обход постзаказа. На этот раз для каждого черного узла мы используем операцию поиска объединения- поиска (со старой меткой ), чтобы найти и присвоить его новую метку (связанную с компонентом связности, частью которого является).${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

Генерация сетки с использованием квадродеревьев [ править ]

В этом разделе кратко излагается глава из книги Хар-Пеледа и де Берга и др. ^{[23] [24]}

Генерация сетки - это, по сути, триангуляция набора точек, для которого может выполняться дальнейшая обработка. Таким образом, желательно, чтобы результирующая триангуляция имела определенные свойства (например, неоднородность, треугольники, которые не являются "слишком тонкими", большие треугольники в разреженных областях и маленькие треугольники в плотных областях и т. Д.), Чтобы ускорить дальнейшую обработку и менее подвержен ошибкам. Кваддеревья, построенные на основе набора точек, могут использоваться для создания сеток с этими желаемыми свойствами.

Рассмотрим лист квадродерева и соответствующую ему клетку . Мы говорим , является сбалансированным (для сетчатого поколения) , если стороны ячейки пересекаются в угловых точках соседних ячеек не более одного раза на каждой стороне. Это означает, что уровни квадродерева соседних листьев отличаются не более чем на единицу от уровня . Когда это верно для всех листьев, мы говорим, что все дерево квадрантов сбалансировано (для генерации сетки).${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

Рассмотрим ячейку и окрестности ячеек одинакового размера с центром в . Мы называем эту окрестность расширенным кластером . Мы говорим, что квадродерево хорошо сбалансировано, если оно сбалансировано, и для каждого листа, который содержит точку из набора точек, его расширенный кластер также находится в дереве квадратов, а расширенный кластер не содержит другой точки из набора точек.${\displaystyle v}$${\displaystyle 5\times 5}$${\displaystyle v}$${\displaystyle u}$

Создание сетки выполняется следующим образом:

1. Постройте квадродерево по входным точкам.
2. Убедитесь, что дерево квадрантов сбалансировано. Для каждого листа, если есть слишком большой сосед, разделите его на части. Это повторяется до тех пор, пока дерево не будет сбалансировано. Мы также следим за тем, чтобы для листа с точкой узлы расширенного кластера каждого листа находились в дереве.
3. Для каждого листового узла , содержащего точку, если расширенный кластер содержит еще одну точку, мы дополнительно разделяем дерево и при необходимости повторно балансируем. Если нам нужно было разделить, для каждого дочернего элемента мы гарантируем, что узлы расширенного кластера находятся в дереве (и при необходимости повторно балансируем).${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$
4. Повторяйте предыдущий шаг, пока дерево не станет хорошо сбалансированным.
5. Преобразуйте квадратное дерево в триангуляцию.

Мы рассматриваем угловые точки ячеек дерева как вершины нашей триангуляции. Перед этапом трансформации у нас есть набор прямоугольников с точками в некоторых из них. Шаг преобразования выполняется следующим образом: для каждой точки деформируйте ближайший угол ее ячейки, чтобы он встретился с ней, и триангулируйте полученные четыре четырехугольника, чтобы получились «красивые» треугольники (заинтересованный читатель отсылается к главе 12 Har-Peled ^{[ 23]} для более подробной информации о том, что делает треугольники «красивыми»).

Остальные квадраты триангулируются по некоторым простым правилам. Для каждого правильного квадрата (без точек внутри и без углов на его сторонах) введите диагональ. Обратите внимание, что из-за способа, которым мы разделяли точки со свойством хорошей балансировки, ни один квадрат с углом, пересекающим сторону, не является квадратом, который был деформирован. Таким образом, мы можем триангулировать квадраты с пересекающимися углами следующим образом. Если есть одна пересекающаяся сторона, квадрат становится тремя треугольниками, добавляя длинные диагонали, соединяющие пересечение с противоположными углами. Если есть четыре пересекающихся стороны, мы разделяем квадрат пополам, добавляя ребро между двумя из четырех пересечений, а затем соединяем эти две конечные точки с двумя оставшимися точками пересечения. Для остальных квадратовмы вводим точку в середине и соединяем ее со всеми четырьмя углами квадрата, а также с каждой точкой пересечения.

В конце концов, у нас есть хорошая триангулированная сетка нашего набора точек, построенная из квадродерева.

Псевдокод [ править ]

Следующий псевдокод показывает одно из средств реализации квадродерева, которое обрабатывает только точки. Доступны и другие подходы.

Предпосылки [ править ]

Предполагается, что эти конструкции используются.

// Простой координатный объект для представления точек и векторов struct XY{ float x; float y; функция __construct ( float _x, float _y) {...}}// Выровненный по оси ограничивающий прямоугольник с половинным размером и центральной структурой AABB{ XY центр; float halfDimension; function __construct ( XY center, float halfDimension) {...} function containsPoint ( XY point) {...} function beansAABB ( AABB other) {...}}

Класс QuadTree [ править ]

Этот класс представляет как одно четырехугольное дерево, так и узел, в котором оно коренится.

класс QuadTree{ // Произвольная константа, указывающая, сколько элементов может быть сохранено в этом узле четырехугольника.  Константа int QT_NODE_CAPACITY = 4; // Выровненный по оси ограничивающий прямоугольник, сохраненный как центр с половинными размерами // для представления границ этого дерева квадратов Граница AABB ; // Точки в этом узле четырехугольного дерева  Массив точек XY [size = QT_NODE_CAPACITY] ; //  Дочерние QuadTree * northWest; QuadTree * northEast; QuadTree * southWest; QuadTree * southEast; // Методы  function __construct ( AABB _boundary) {...} function insert ( XY p) {...} function subdivide () {...} // создать четыре дочерних элемента, которые полностью разделяют этот четырехугольник на четыре четырехугольника равной площади  функция queryRange ( диапазон AABB ) {...}}

Вставка [ править ]

Следующий метод вставляет точку в соответствующий квадрат дерева квадрантов, при необходимости разделяя ее.

класс QuadTree{ ...  // Вставляем точку в  функцию QuadTree insert ( XY p) { // Игнорировать объекты, которые не принадлежат этому дереву квадратов  if (! Border.containsPoint (p)) return  false ; // объект не может быть добавлен  // Если в этом дереве квадратов есть место и если у него нет подразделений, добавьте сюда объект if (points.size <QT_NODE_CAPACITY && northWest == null ) { points.append (p); вернуть  истину ; }  // В противном случае разделите и затем добавьте точку к любому узлу, который примет ее  if (northWest == null ) subdivide (); // Мы должны добавить точки / данные, содержащиеся в этом массиве четырехугольников, в новые четырехугольники, если мы хотим, чтобы  // только последний узел содержал данные  если (northWest-> insert (p)) вернет  истину ; если (север-восток-> вставить (р)) вернуть  истину ; если (юг-запад-> вставить (р)) вернет  истину ; если (юг-восток-> вставить (р)) вернуть  истину ;  // В противном случае точка не может быть вставлена ​​по неизвестной причине (этого никогда не должно происходить)  return  false ; }}

Диапазон запроса [ править ]

Следующий метод находит все точки, содержащиеся в диапазоне.

класс QuadTree{ ...  // Находим все точки, которые появляются в пределах диапазона  function queryRange ( диапазон AABB ) { // Подготавливаем массив результатов  Array of XY pointsInRange;  // Автоматическое прерывание, если диапазон не пересекает этот четырехугольник  if (! Border.intersectsAABB (range)) return pointsInRange; // пустой список  // Проверяем объекты на этом уровне четырехугольника  на ( int p = 0; p <points.size; p ++) { если (range.containsPoint (points [p])) pointsInRange.append (points [p]); }  // Завершаем здесь, если потомков нет  if (northWest == null ) return pointsInRange;  // В противном случае складываем точки от потомков pointsInRange.appendArray (northWest-> queryRange (диапазон)); pointsInRange.appendArray (northEast-> queryRange (диапазон)); pointsInRange.appendArray (southWest-> queryRange (диапазон)); pointsInRange.appendArray (юг-восток-> queryRange (диапазон));  return pointsInRange; }}

См. Также [ править ]

• Адаптивное уточнение сетки
• Разделение двоичного пространства
• Бинарная мозаика
• Kd-дерево
• Octree
• R-дерево
• УБ-дерево
• Пространственная база данных
• Подмощение
• Кривая Z-порядка

Ссылки [ править ]

Обзоры Алуру ^[4] и Самета ^{[21] [15]} дают хороший обзор квадродеревьев.

Примечания [ править ]

Общие ссылки [ править ]

1. Рафаэль Финкель и Дж. Л. Бентли (1974). "Quad Trees: структура данных для поиска по составным ключам". Acta Informatica . 4 (1): 1–9. DOI : 10.1007 / BF00288933 . S2CID  33019699 .
2. Марк де Берг , Марк ван Кревельд , Марк Овермарс и Отфрид Шварцкопф (2000). Вычислительная геометрия (2-е изд., Перераб.). Springer-Verlag . ISBN 3-540-65620-0.CS1 maint: multiple names: authors list (link) Глава 14: Quadtrees: стр. 291–306.
3. Самет, Ханан ; Уэббер, Роберт (июль 1985). «Сохранение набора полигонов с помощью квадродеревьев» (PDF) . Проверено 23 марта 2012 года .