Квадратно стабло
| Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Квадратно стабло је врста бинарног стабла чији сваки унутрашњи чвор има тачно четворо деце. Квадратна стабла најчешће се користе за поделу дводимензионалног простора рекурзивном паралелизацијом у четири квадранта или регије. Регије могу бити квадратног или правоугаоног облика, или могу имати произвољне облике. Рафаел Финкел и Џон Бентли дали су назив овој структури података,Квадратно стабло, 1974. године. Квадратно стабло је такође познато и као Q-стабло.
Све форме квадратног стабла деле неке заједничке карактеристике:
- Разлажу простор у прилагодљиве ћелије
- Свака ћелија има максимални капацитет. Када се достигне максимални капацитет,ћелија се дели
- Стабло директоријум прати просторну декомпозицију квадратног стабла
Врсте
уредиКвадратна стабла могу се класификовати према врсти података које они представљају,укључујући регије,тачке,праве и криве. Квадратна стабла такође могу бити класификована по томе да ли је облик стабла независан од редоследа података који обрађује. Неки уобичајени типови су:
Регионско квадратно стабло
уредиРегионско квадратно стабло представља поделу простора у две димензије тако што разлаже регију на четири једнака квадранта,подквадранта и тако даље, сваки лисни чвор садржи податке који одговарају одређеном подрегиону. Сваки чвор у стаблу или има тачно четворо деце, или нема децу (лисни чвор).
Регионско квадратно стабло је врста стабла. Регионско квадратно стабло дубине н може бити коришћено за представљање слике 2н x 2н пиксела, где је сваки пиксел вредности 0 или 1. Корени чвор представља цео регион слике. Ако пиксели у било којој регији нису искључиво нуле или јединице,она је подељена. У овој пријави,сваки лисни чвор представља блок пиксела који су све нуле или све јединице.
Регионско квадратно стабло такође мозе бити коришћено као репрезентација променљиве резолуције поља података.Ако се регионско квадратно стабло користи при представљању скупа тачака података(као што су географска ширина и дужина скупа градова),региони су подељени док један лист садржи највише једну тачку.[1]
Тачкасто квадратно стабло
уредиТачкасто квадратно стабло комбинује приступ грид структура са вишедимензионалном генерализацијом стабла бинарног претраживања. Сваки грански(не-лисни) чвор је повезан са податковним записом са локацијом тачке и има четири следбеника (НW,НЕ,СW и СЕ). Свака квадрантска подела је центрирана над податковном тачком. Време развоја(израде) квадратног стабла је О(н лог н), а време тражења је О(лог н).[2]
Структура чвора за Тачкасто квадратно стабло
уредиЧвор тачкастог квадратног стабла је сличан чвору бинарног стабла, са главном разликом у томе што има четири показивача(један за сваки квадрант) уместо два("леви" и "десни") као у уобичајеном бинарном стаблу. Такође,кључ се обично декомпонује на два дела,које се односе на x и y координате. Зато чвор садржи следеће податке:
- четири показивача:['НW'],['НЕ'],['СW'], и ['СЕ']
- тачку; што заузврат садржи:
- кључ, обично изражен као x,y координате
- вредност; на пример име
Рубно квадратно стабло
уредиРубна квадратна стабла се обично користе за чување линија више него за чување тачака. Криве су апроксимиране паралелизацијом ћелија у веома фине резолуције. Ово може довести до изузетно неуравнотежених стабала која могу анулирати сврху индексирања.
Полигонална мапа квадратног стабла
уредиПолигонална мапа квадратног стабла (или ПМ Квадратно стабло) је варијација квадратног стабла, која се користи за складиштење колекције полигона која могу бити дегенерисана(што значи да су изолована темена или ивице).[1] Постоје три главне класе ПМ Квадратних стабала које варирају у зависности од тога које информације чувају унутар сваког црног чвора. ПМ3 квадратна стабла могу да складиште било коју величину ивица које се не секу и највише једну тачку. ПМ2 квадратна стабла су иста као ПМ3 квадратна стабла, осим што све ивице морају да деле исту крајњу тачку. Коначно,ПМ1 квадратна стабла слична су ПМ2, али у овом случају црни чворови могу да или садрже тачку и његове ивице, или да садрже скуп ивица које деле једну тачку , али не може имати тачку и скуп ивица које не садрже ту тачку.
- Репрезентација Квадратног стабла
- Просторно индексирање
- Ефикасно откривање судара у две димензије
- Цонwаy'с Гаме оф Лифе програм.[3]
- Квадратна стабла се такође користе у области фракталне анализе слике
Псеудокод
уредиСледећи псеудокод показује један начин имплементације квадратног стабла који користи само тачке. Постоје и други приступи на располагању.
Предуслови
уредиПретпоставља се да су ове структуре коришћене.
struct XY
{
float x;
float y;
function __construct(float _x, float _y) {...}
}
struct AABB
{
XY center;
XY halfDimension;
function __construct(XY center, XY halfDimension) {...}
function containsPoint(XY p) {...}
function intersectsAABB(AABB other) {...}
}
Класа квадратног стабла
уредиОва класа представља и квадратно стабло и чвор где је укорењен
class QuadTree
{
constant int QT_NODE_CAPACITY = 4;
AABB boundary;
Array of XY [size = QT_NODE_CAPACITY] points;
// Deca
QuadTree* northWest;
QuadTree* northEast;
QuadTree* southWest;
QuadTree* southEast;
// Metode
function __construct(AABB _boundary) {...}
function insert(XY p) {...}
function subdivide() {...}
function queryRange(AABB range) {...}
}
Уметање
уредиСледећи метод убацује тачку у одговарајући квадрат квадратног стабла.
class QuadTree
{
...
// Ubacujemo tačku u kvadratno stablo
function insert(XY p)
{
// Zanemarujemo objekte koji ne pripadaju ovom kvadratnom stablu
if (!boundary.containsPoint(p))
return false;
// Ako ima mesta u ovom kvadratnom stablu,dodajemo objekat ovde
if (points.size < QT_NODE_CAPACITY)
{
points.append(p);
return true;
}
// U suprotnom,moramo podeliti na manje delove,zatim dodati tačku bilo kojem čvoru koji će to prihvatiti
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;
// Inače,tačka neće biti ubačena iz nekog nepoznatog razloga
return false;
}
}
Испитивање опсега
уредиСледећи метод проналази све тачке које се налазе у опсегу.
class QuadTree
{
...
//Pronalazimo sve tačke koje se pojavljuju unutar opsega
function queryRange(AABB range)
{
// Priprema se niz rezultata
Array of XY pointsInRange;
// Automatski prekid ukoliko se opseg ne podudara sa ovim kvadratom
if (!boundary.intersectsAABB(range))
return pointsInRange; // empty list
// Provera objekata
for (int p := 0; p < points.size; p++)
{
if (range.containsPoint(points[p]))
pointsInRange.append(points[p]);
}
// Prekida se ovde,ako nema dece
if (northWest == null)
return pointsInRange;
// U suprotnom,dodajemo tačke koje pripadaju deci
pointsInRange.appendArray(northWest->queryRange(range));
pointsInRange.appendArray(northEast->queryRange(range));
pointsInRange.appendArray(southWest->queryRange(range));
pointsInRange.appendArray(southEast->queryRange(range));
return pointsInRange;
}
}
Референце
уредиБелешке
уреди- ^ а б Ханан Самет анд Роберт Wеббер. "Сторинг а Цоллецтион оф Полyгонс Усинг Qуадтреес". АЦМ Трансацтионс он Грапхицс Јулy (1985), пп. 182-222. ИнфоЛАБ. Wеб. 23 Марцх 2012
- ^ Структуре и методе приступа
- ^ Рокицки, Томас Г. (1. 4. 2006). „Ан Алгоритхм фор Цомпрессинг Спаце анд Тиме”. Приступљено 20. 5. 2009.
Главне референце
уреди- Финкел, Рапхаел; Ј.L. Бентлеy (1974). „Qуад Треес: А Дата Струцтуре фор Ретриевал он Цомпосите Кеyс”. Ацта Информатица. 4 (1): 1—9. дои:10.1007/БФ00288933.
- Марк де Берг; et al. (2000). „Qуадтреес”. Цомпутатионал Геометрy (2нд ревисед изд.). Спрингер-Верлаг. стр. 291–306. ИСБН 978-3-540-65620-3.
- Самет, Ханан; Wеббер, Роберт (јул 1985). „Сторинг а Цоллецтион оф Полyгонс Усинг Qуадтреес” (ПДФ). Архивирано из оригинала (ПДФ) 17. 06. 2012. г. Приступљено 23. 3. 2012.
