| Fire-Run | Дата: Среда, 19.12.2018, 12:29 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 43
Статус: Оффлайн
| Quad TreeЧетыре дерева - это деревья, используемые для эффективного хранения данных точек в двумерном пространстве. В этом дереве каждый узел имеет не более четырех дочерних элементов.
Мы можем построить квадродерево из двумерной области, используя следующие шаги:
Разделите текущее двухмерное пространство на четыре поля.
Если в блоке содержится одна или несколько точек, создайте дочерний объект, сохранив в нем двухмерное пространство блока.
Если поле не содержит точек, не создавайте для него дочерний элемент
Рекурс для каждого из детей.
Четыре дерева используются в сжатии изображений, где каждый узел содержит средний цвет каждого из его дочерних элементов. Чем глубже вы проходите по дереву, тем больше деталей изображения.
Четыре дерева также используются при поиске узлов в двумерной области. Например, если вы хотите найти ближайшую точку к заданным координатам, вы можете сделать это с помощью четырех деревьев.
Функция вставки Функции
вставки используются для вставки узла в существующее дерево квадов. Эта функция сначала проверяет, находится ли данный узел в границах текущего четырехугольника. Если это не так, то мы немедленно прекращаем вставку. Если он находится в пределах границ, мы выбираем соответствующий дочерний элемент для размещения этого узла в зависимости от его местоположения.
Эта функция - O (Log N), где N - размер расстояния.
Функция поиска Функция
поиска используется для определения местоположения узла в данном квадре. Его также можно изменить, чтобы он возвращал ближайший узел к заданной точке. Эта функция реализуется путем взятия заданной точки, сравнения с границами дочерних квадратов и рекурсии.
Эта функция - O (Log N), где N - размер расстояния.
Рекомендуется: Пожалуйста, сначала попробуйте подход {IDE} , прежде чем переходить к решению.
Программа, приведенная ниже, демонстрирует хранение узлов в дереве квадрантов.
Код // C++ Implementation of Quad Tree #include <iostream> #include <cmath> using namespace std; // Used to hold details of a point struct Point { int x; int y; Point(int _x, int _y) { x = _x; y = _y; } Point() { x = 0; y = 0; } }; // The objects that we want stored in the quadtree struct Node { Point pos; int data; Node(Point _pos, int _data) { pos = _pos; data = _data; } Node() { data = 0; } }; // The main quadtree class class Quad { // Hold details of the boundary of this node Point topLeft; Point botRight; // Contains details of node Node *n; // Children of this tree Quad *topLeftTree; Quad *topRightTree; Quad *botLeftTree; Quad *botRightTree; public: Quad() { topLeft = Point(0, 0); botRight = Point(0, 0); n = NULL; topLeftTree = NULL; topRightTree = NULL; botLeftTree = NULL; botRightTree = NULL; } Quad(Point topL, Point botR) { n = NULL; topLeftTree = NULL; topRightTree = NULL; botLeftTree = NULL; botRightTree = NULL; topLeft = topL; botRight = botR; } void insert(Node*); Node* search(Point); bool inBoundary(Point); }; // Insert a node into the quadtree void Quad::insert(Node *node) { if (node == NULL) return; // Current quad cannot contain it if (!inBoundary(node->pos)) return; // We are at a quad of unit area // We cannot subdivide this quad further if (abs(topLeft.x - botRight.x) <= 1 && abs(topLeft.y - botRight.y) <= 1) { if (n == NULL) n = node; return; } if ((topLeft.x + botRight.x) / 2 >= node->pos.x) { // Indicates topLeftTree if ((topLeft.y + botRight.y) / 2 >= node->pos.y) { if (topLeftTree == NULL) topLeftTree = new Quad( Point(topLeft.x, topLeft.y), Point((topLeft.x + botRight.x) / 2, (topLeft.y + botRight.y) / 2)); topLeftTree->insert(node); } // Indicates botLeftTree else { if (botLeftTree == NULL) botLeftTree = new Quad( Point(topLeft.x, (topLeft.y + botRight.y) / 2), Point((topLeft.x + botRight.x) / 2, botRight.y)); botLeftTree->insert(node); } } else { // Indicates topRightTree if ((topLeft.y + botRight.y) / 2 >= node->pos.y) { if (topRightTree == NULL) topRightTree = new Quad( Point((topLeft.x + botRight.x) / 2, topLeft.y), Point(botRight.x, (topLeft.y + botRight.y) / 2)); topRightTree->insert(node); } // Indicates botRightTree else { if (botRightTree == NULL) botRightTree = new Quad( Point((topLeft.x + botRight.x) / 2, (topLeft.y + botRight.y) / 2), Point(botRight.x, botRight.y)); botRightTree->insert(node); } } } // Find a node in a quadtree Node* Quad::search(Point p) { // Current quad cannot contain it if (!inBoundary(p)) return NULL; // We are at a quad of unit length // We cannot subdivide this quad further if (n != NULL) return n; if ((topLeft.x + botRight.x) / 2 >= p.x) { // Indicates topLeftTree if ((topLeft.y + botRight.y) / 2 >= p.y) { if (topLeftTree == NULL) return NULL; return topLeftTree->search(p); } // Indicates botLeftTree else { if (botLeftTree == NULL) return NULL; return botLeftTree->search(p); } } else { // Indicates topRightTree if ((topLeft.y + botRight.y) / 2 >= p.y) { if (topRightTree == NULL) return NULL; return topRightTree->search(p); } // Indicates botRightTree else { if (botRightTree == NULL) return NULL; return botRightTree->search(p); } } }; // Check if current quadtree contains the point bool Quad::inBoundary(Point p) { return (p.x >= topLeft.x && p.x <= botRight.x && p.y >= topLeft.y && p.y <= botRight.y); } // Driver program int main() { Quad center(Point(0, 0), Point(8, 8)); Node a(Point(1, 1), 1); Node b(Point(2, 5), 2); Node c(Point(7, 6), 3); center.insert(&a); center.insert(&b); center.insert(&c); cout << "Node a: " << center.search(Point(1, 1))->data << "\n"; cout << "Node b: " << center.search(Point(2, 5))->data << "\n"; cout << "Node c: " << center.search(Point(7, 6))->data << "\n"; cout << "Non-existing node: " << center.search(Point(5, 5)); return 0; }
Вывод:
Узел А: 1
Узел б: 2
Узел с: 3
Несуществующий узел: 0
Упражнение:
реализовать дерево квадов, которое возвращает 4 ближайших узла к заданной точке.
|
| |
| |
