Квадтри
Дерево квадрантов — это древовидная структура данных, в которой каждый внутренний узел имеет ровно четыре дочерних элемента. Квадранты являются двумерным аналогом октодеревьев и чаще всего используются для разделения двумерного пространства путем рекурсивного разделения его на четыре квадранта или области. Данные, связанные с листовой ячейкой, различаются в зависимости от приложения, но листовая ячейка представляет собой «единицу интересной пространственной информации».
Разделенные области могут быть квадратными или прямоугольными или могут иметь произвольную форму. Эта структура данных была названа деревом квадрантов Рафаэлем Финкелем и Дж. Л. Бентли в 1974 г. [1] Подобное разбиение также известно как Q-дерево . Все формы деревьев квадрантов имеют некоторые общие черты:
Дерево -пирамида ( Т-пирамида ) — это «полное» дерево; каждый узел Т-пирамиды имеет четыре дочерних узла, кроме листовых узлов; все листья находятся на одном уровне, уровне, который соответствует отдельным пикселям изображения. Данные в древовидной пирамиде могут компактно храниться в массиве как неявная структура данных, подобно тому, как полное двоичное дерево может компактно храниться в массиве . [2]
Quadtrees можно классифицировать в соответствии с типом данных, которые они представляют, включая площади, точки, линии и кривые. Quadtree также можно классифицировать по тому, не зависит ли форма дерева от порядка обработки данных. Ниже приведены распространенные типы деревьев квадрантов.
Дерево квадрантов области представляет собой разделение пространства в двух измерениях путем разложения области на четыре равных квадранта, подквадранта и т. д., при этом каждый конечный узел содержит данные, соответствующие определенной подобласти. Каждый узел в дереве либо имеет ровно четыре дочерних элемента, либо не имеет дочерних элементов (листовой узел). Высота деревьев квадрантов, которые следуют этой стратегии декомпозиции (т. е. подразделению подквадрантов до тех пор, пока в подквадранте есть интересные данные, для которых требуется большее уточнение), чувствительна и зависит от пространственного распределения интересных областей в декомпозируемом пространстве. Дерево квадрантов региона является разновидностью дерева .
Дерево квадрантов области с глубиной n может использоваться для представления изображения, состоящего из 2 n × 2 nпикселей, где значение каждого пикселя равно 0 или 1. Корневой узел представляет всю область изображения. Если пиксели в какой-либо области не полностью равны 0 или 1, она подразделяется. В этом приложении каждый листовой узел представляет собой блок пикселей, состоящих либо из нулей, либо из единиц. Обратите внимание на потенциальную экономию места, когда эти деревья используются для хранения изображений; изображения часто имеют много областей значительного размера, которые имеют одинаковое цветовое значение. Вместо того, чтобы хранить большой двумерный массив каждого пикселя изображения, дерево квадрантов может захватывать ту же информацию, потенциально на много уровней деления выше, чем ячейки с разрешением в пикселях, которые нам в противном случае потребовались бы. Разрешение дерева и общий размер ограничены размерами пикселей и изображения.
