Квадрантное дерево
-
Квадрантные деревья
- Древовидная структура данных с четырьмя дочерними узлами на каждом внутреннем узле
- Используются для разбиения двумерного пространства на квадранты
- Данные хранятся в листовых ячейках, представляющих единицы пространственной информации
-
Типы квадрантных деревьев
- Регион квадрантное дерево: разбиение пространства на четыре квадранта, высота зависит от распределения данных
- Область квадрантное дерево: представление изображения, экономия места за счет хранения блоков пикселей
- Точечное квадрантное дерево: адаптация бинарного дерева для точечных данных, высота зависит от порядка вставки точек
- Дерево квадрантов Точка-область (PR): хранение списка точек в ячейках, высота зависит от пространственного распределения точек
- Реберное квадрантное дерево: хранение линий, высокое разрешение вблизи углов, может быть несбалансированным
- Дерево квадрантов полигональной карты (PM): хранение многоугольников, три класса: PM3, PM2, PM1
-
Сжатые квадрантные деревья
- Сокращение размера деревьев путем сохранения только важных поддеревьев
- Использование кривых Z-порядка для логарифмического поиска, вставки и удаления
- Определение местоположения точки в сжатом дереве за O(log n) время
-
Использование квадрантных деревьев
- Квадрантные деревья используются для представления изображений, обработки изображений, генерации сетки, пространственной индексации и других задач.
- Они также применяются в фрактальном анализе изображений и оценке состояния.
-
Объединение и пересечение изображений
- Объединение изображений выполняется быстро и эффективно с помощью квадрантных деревьев.
- Пересечение изображений выполняется аналогично, но с заменой черного и белого.
-
Маркировка подключенных компонентов
- Алгоритм Самета позволяет находить и помечать связанные компоненты в двоичных изображениях.
- Он работает в три этапа: установление отношений смежности, обработка эквивалентности и пометка черных пикселей.
-
Генерация сетки с использованием квадрантных деревьев
- Квадрантные деревья могут использоваться для создания сеток с желаемыми свойствами.
- Дерево квадрантов должно быть сбалансировано и хорошо сбалансировано для генерации сетки.
- Процесс генерации сетки включает построение дерева, его балансировку и преобразование в триангуляцию.
-
Преобразование квадрата в треугольники
- Если есть одна пересекающаяся сторона, квадрат превращается в три треугольника путем добавления длинных диагоналей.
- Если есть четыре пересекающиеся стороны, квадрат делится пополам, добавляется ребро между двумя точками пересечения, затем соединяются конечные точки с оставшимися двумя точками.
- Для остальных квадратов вводится точка посередине и соединяется со всеми углами и точками пересечения.
-
Псевдокод и предпосылки
- Псевдокод показывает один из способов реализации дерева квадрантов.
- Предполагается использование определенных структур данных.
-
Класс квадродеревьев
- Класс представляет собой как дерево квадрантов, так и узел, в котором оно находится.
-
Вставка
- Метод вставляет точку в соответствующий квадрат дерева квадрантов, при необходимости разделяя его.
-
Диапазон запросов
- Метод позволяет найти все точки, содержащиеся в пределах диапазона.
-
Связанные структуры данных
- Адаптивное уточнение сетки
- Разбиение двоичного пространства на разделы
- Бинарная черепица
- дерево k-d
- Восьмиугольное дерево
- R-дерево
- UB-дерево
- Пространственная база данных
- Подмачивание
- Кривая Z-порядка
-
Рекомендации
- Обзоры Aluru[4] и Samet[22][16] дают хороший обзор квадрантных деревьев.
- Общие рекомендации
- CS1 основное: несколько названий: список авторов (ссылка) Глава 14: Квадрантные деревья: стр. 291–306.