Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Дерево квадрантів також квадродерево 4 дерево англ quadtree дерево в якому у кожного внутрішнього вузла рівно чотири нащ

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

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

Дерево квадрантів (також квадродерево, 4-дерево, англ. quadtree) — дерево, в якому у кожного внутрішнього вузла рівно чотири нащадки. Дерева квадрантів можуть використовуватися для рекурсивного розбиття двовимірного простору по 4 квадранти (області). Області представляють собою квадрати, прямокутники або мають довільну форму. Англомовний термін quadtree був придуманий [en] і [en] в 1974 році. Аналогічне розділення простору відомо як Q-дерево. Загальні риси різних видів дерев квадрантів:

  • розбиття простору на адаптивні секції (англ. adaptable cells)
  • максимальний розмір кожної секції
  • відповідність напряму дерева просторому розподіленню.
image
Площина, розбита за допомогою дерева квадрантів
image
Поступове стиснення зображення за допомогою дерева квадрантів. Зліва показано стиснене зображення з границями комірок, а праворуч - лише стиснене зображення

Дерево-піраміда (англ. tree-pyramid, T-pyramid) це "повне" дерево; кожна вершина Д-піраміди має чотири дитини, окрім вершин-листів; усі листи знаходяться на одному рівні, де рівень відповідає за характерний піксель на зображенні. Дані в дереві-піраміді можна компактно зберігати в масиві як неявну структуру даних подібно до того, як повне двійкове дерево може бути компактно збережене в масиві.

Класифікація

Дерева квадрантів можуть бути класифіковані відповідно до типу даних та факту залежності від порядку їх обробки.

Region quadtree

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

Point quadtree

Дерева квадрантів точок (англ. point quadtree), — різновид бінарних дерев, що використовуються для зберігання інформації про точки на площині. Форма дерева залежить від порядку даних. Використання таких дерев є ефективним для задач порівняння впорядкованих двовимірних точок площини, маючи складність O(log n). Структура вузла дерева квадрантів, що зберігає інформацію про точки площини, є аналогічною структурі вузла бінарного дерева. Відмінність полягає лише в наявності у першого чотирьох нащадків (по одному на кожен квадрант) замість двох («правого» і «лівого») у другого. Ключ вузла складається з двох компонент (координат x і y).

Edge quadtree

Дерева квадрантів ліній (англ. edge quadtree), використовуються для представлення прямих і кривих. Шляхом апроксимації криві розбиваються на дрібні відрізки, кожен з яких належить до окремого листового вузла. Такий спосіб може призвести до розбалансування дерева, що буде означати проблеми з індексацією.

Polygonal map quadtree

Дерева квадрантів, що зберігають інформацію про многокутники (англ. polygonal map quadtree/PMQuadtree), можуть містити інформацію про полігони, у тому числі ті, які мають ізольовані вершини або межі.

Способи використання

Дерева квадрантів є двомірним аналогом дерев октантів (англ. 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

Клас одночасно виконує роль вузла дерева квадрантів та надає інтерфейс структури даних. 

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(XYp) { // Ігнорувати об'єкти, що не належать дереву 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(AABBrange) { // Підготувати масив під результат Array of XYpointsInRange; // Скасування, якщо діапазон не збігається з квадрантом 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 (1 квітня 2006). An Algorithm for Compressing Space and Time. Архів оригіналу за 2 жовтня 2012. Процитовано 20 травня 2009.
  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 (2000). Computational Geometry (вид. 2nd revised). Springer-Verlag. ISBN . Chapter 14: Quadtrees: pp. 291–306.
  3. Storing a Collection of Polygons Using Quadtrees (PDF). July 1985. Архів оригіналу (PDF) за 2 жовтня 2012. Процитовано 23 березня 2012.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Derevo kvadrantiv takozh kvadroderevo 4 derevo angl quadtree derevo v yakomu u kozhnogo vnutrishnogo vuzla rivno chotiri nashadki Dereva kvadrantiv mozhut vikoristovuvatisya dlya rekursivnogo rozbittya dvovimirnogo prostoru po 4 kvadranti oblasti Oblasti predstavlyayut soboyu kvadrati pryamokutniki abo mayut dovilnu formu Anglomovnij termin quadtree buv pridumanij en i en v 1974 roci Analogichne rozdilennya prostoru vidomo yak Q derevo Zagalni risi riznih vidiv derev kvadrantiv rozbittya prostoru na adaptivni sekciyi angl adaptable cells maksimalnij rozmir kozhnoyi sekciyi vidpovidnist napryamu dereva prostoromu rozpodilennyu Ploshina rozbita za dopomogoyu dereva kvadrantiv Postupove stisnennya zobrazhennya za dopomogoyu dereva kvadrantiv Zliva pokazano stisnene zobrazhennya z granicyami komirok a pravoruch lishe stisnene zobrazhennya Derevo piramida angl tree pyramid T pyramid ce povne derevo kozhna vershina D piramidi maye chotiri ditini okrim vershin listiv usi listi znahodyatsya na odnomu rivni de riven vidpovidaye za harakternij piksel na zobrazhenni Dani v derevi piramidi mozhna kompaktno zberigati v masivi yak neyavnu strukturu danih podibno do togo yak povne dvijkove derevo mozhe buti kompaktno zberezhene v masivi KlasifikaciyaDereva kvadrantiv mozhut buti klasifikovani vidpovidno do tipu danih ta faktu zalezhnosti vid poryadku yih obrobki Region quadtree Derevo kvadrantiv oblasti vikonuye rozdil dvovimirnogo prostoru rekursivno rozkladayuchi jogo na chotiri rivnih kvadrati de kozhen terminalnij listovij vuzol mistit dani sho vidpovidayut konkretnomu subregionu Taki strukturi vidnosyatsya do tipu prefiksnih derev Point quadtree Dereva kvadrantiv tochok angl point quadtree riznovid binarnih derev sho vikoristovuyutsya dlya zberigannya informaciyi pro tochki na ploshini Forma dereva zalezhit vid poryadku danih Vikoristannya takih derev ye efektivnim dlya zadach porivnyannya vporyadkovanih dvovimirnih tochok ploshini mayuchi skladnist O log n Struktura vuzla dereva kvadrantiv sho zberigaye informaciyu pro tochki ploshini ye analogichnoyu strukturi vuzla binarnogo dereva Vidminnist polyagaye lishe v nayavnosti u pershogo chotiroh nashadkiv po odnomu na kozhen kvadrant zamist dvoh pravogo i livogo u drugogo Klyuch vuzla skladayetsya z dvoh komponent koordinat x i y Edge quadtree Dereva kvadrantiv linij angl edge quadtree vikoristovuyutsya dlya predstavlennya pryamih i krivih Shlyahom aproksimaciyi krivi rozbivayutsya na dribni vidrizki kozhen z yakih nalezhit do okremogo listovogo vuzla Takij sposib mozhe prizvesti do rozbalansuvannya dereva sho bude oznachati problemi z indeksaciyeyu Polygonal map quadtree Dereva kvadrantiv sho zberigayut informaciyu pro mnogokutniki angl polygonal map quadtree PMQuadtree mozhut mistiti informaciyu pro poligoni u tomu chisli ti yaki mayut izolovani vershini abo mezhi Sposobi vikoristannyaPredstavlennya zobrazhen Prostorovi bazi danih Efektivne viyavlennya zitknen u dvovimirnomu prostori Vidsikannya nevidimih chastin landshaftu angl en Zberigannya danih tablichnih abo matrichnih obchislen Obchislennya pov yazani z bagatovimirnimi polyami obchislyuvalna gidrodinamika elektromagnetizm Simulyaciya gri Zhittya Obchislennya staniv dinamichnoyi sistemi za yakoyu vedetsya sposterezhennya Analiz chastin fraktalnih zobrazhen Dereva kvadrantiv ye dvomirnim analogom derev oktantiv angl octree PsevdokodPrivedenij psevdokod demonstruye vikoristannya derev kvadrantiv dlya zberigannya informaciyi pro ob yekti Mozhlivi j inshi pidhodi do pobudovi takoyi strukturi danih Strukturi danih Peredbachayetsya vikoristannya nastupnih struktur danih Prosta struktura dlya predstavlennya tochki abo vektora struct XY float x float y function construct float x float y Obmezhuye paralelepiped virivnyanij po koordinatnim osyam axis aligned bounding box AABB polovinnoyi rozmirnosti z centrom struct AABB XY center XY halfDimension function construct XY center XY halfDimension function containsPoint XY p function intersectsAABB AABB other Klas QuadTree Klas odnochasno vikonuye rol vuzla dereva kvadrantiv ta nadaye interfejs strukturi danih class QuadTree Konstanta kilkist elementiv yaki mozhna zberigati v odnomu vuzli constant int QT NODE CAPACITY 4 Obmezhuye paralelepiped virivnyanij po koordinatnim osyam pokazuye mezhi dereva AABB boundary Tochki Array of XY size QT NODE CAPACITY points Nashadki QuadTree northWest QuadTree northEast QuadTree southWest QuadTree southEast Metodi function construct AABB boundary function insert XY p function subdivide Stvorennya 4 nashadkiv yaki podilyayut kvadrant na 4 rivni chastini function queryRange AABB range Vstavka Nastupnij metod zdijsnyuye vstavku ob yekta u vidpovidnij kvadrant dereva zdijsnyuyuchi rozbittya yaksho ce neobhidno classQuadTree Vstaviti tochku function insert XYp Ignoruvati ob yekti sho ne nalezhat derevu if boundary containsPoint p return false Ob yekt ne mozhe buti dodanij Yaksho ye misce zdijsniti vstavku if points size lt QT NODE CAPACITY points append p return true Inakshe rozdiliti oblast na chotiri i dodati ob yekti v potribnij vuzol if northWest null subdivide if northWest gt insert p return true if northEast gt insert p return true if southWest gt insert p return true if southEast gt insert p return true return false Vhodzhennya v diapazon Nastupnij metod znahodit vsi ob yekti sho vhodyat v diapazon classQuadTree Znajti ob yekti sho vhodyat v diapazon function queryRange AABBrange Pidgotuvati masiv pid rezultat Array of XYpointsInRange Skasuvannya yaksho diapazon ne zbigayetsya z kvadrantom if boundary insersectsAABB range return pointsInRange Porozhnij spisok Pereviriti ob yekti potochnogo rivnya for int p 0 p lt points size p if range containsPoint points p pointsInRange append points p Zupinitis yaksho bilshe nemaye nashadkiv if northWest null returnpointsInRange Inakshe dodati vsi tochki nashadkiv pointsInRange appendArray northWest gt queryRange range pointsInRange appendArray northEast gt queryRange range pointsInRange appendArray southWest gt queryRange range pointsInRange appendArray southEast gt queryRange range returnpointsInRange PrimitkiHanan Samet and Robert Webber Storing a Collection of Polygons Using Quadtrees ACM Transactions on Graphics July 1985 182 222 InfoLAB Web 23 March 2012 Tomas G Rokicki 1 kvitnya 2006 An Algorithm for Compressing Space and Time Arhiv originalu za 2 zhovtnya 2012 Procitovano 20 travnya 2009 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 DzherelaRaphael 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 Mark de Berg Marc van Kreveld Mark Overmars and Otfried Schwarzkopf 2000 Computational Geometry vid 2nd revised Springer Verlag ISBN 3 540 65620 0 Chapter 14 Quadtrees pp 291 306 Storing a Collection of Polygons Using Quadtrees PDF July 1985 Arhiv originalu PDF za 2 zhovtnya 2012 Procitovano 23 bereznya 2012

Дата публікації:
Топ