h2. Introducere
In acest articol voi discuta despre cateva structuri de date folositoare pentru probleme de geometrie, in special pentru probleme ortogonale. **Problema de baza** ce va fi rezolvata suna in felul urmator: avem n puncte in plan si pentru un anumit dreptunghi ne intereseaza numarul de puncte din acel dreptunghi, sau diverse alte operatii pentru punctele din interiorul sau, cum ar fi suma cheilor punctelor, minimul sau maximul cheilor (daca punctele au asociate cate o cheie). Folosind arbori de intervale putem rezolva aceasta problema, dar vreau sa exemplific ce alte variante mai avem si avantajele lor, precum si aplicatii practice pentru cautarea pe domenii ortogonale. In general, abordarile prezentate mai jos se pot extinde de la cazul unidimensional sau bidimensional, cu usurinta, la cazuri N-dimensionale.
In acest articol voi discuta despre cateva structuri de date folositoare pentru probleme de geometrie, in special pentru probleme ortogonale. **Problema de baza** ce va fi rezolvata suna in felul urmator: avem $n$ puncte in plan si pentru un anumit dreptunghi ne intereseaza numarul de puncte din acel dreptunghi, sau diverse alte operatii pentru punctele din interiorul sau, cum ar fi suma cheilor punctelor, minimul sau maximul cheilor (daca punctele au asociate cate o cheie). Folosind arbori de intervale putem rezolva aceasta problema, dar vreau sa exemplific ce alte variante mai avem si avantajele lor, precum si aplicatii practice pentru cautarea pe domenii ortogonale. In general, abordarile prezentate mai jos se pot extinde de la cazul unidimensional sau bidimensional, cu usurinta, la cazuri N-dimensionale.
Pentru a intelege cat mai bine ideile si structurile de date prezentate mai departe recomand citirea articolelor [1] si [2].
Structurile prezentate sunt in general statice, adica formam intai structura si apoi rezolvam problema. Structurile de date se pot modifica pentru a suporta inserari si stergeri de puncte, devenind dinamice, dar astfel implementarea se complica. Pentru a simula dinamismul putem insera toate datele de la inceput si sa mai avem un camp boolean in care marcam cu true daca data a fost logic inserata si cu false daca data din nodul respectiv nu a fost inca logic inserata. Aceasta pastreaza complexitatea operatiilor pe structura si ne ajuta in echilibrarea structurilor pentru o eficienta buna a operatiilor.
h2. QuadTree
_QuadTree_ este o structura care organizeaza informatii pentru date multidimensionale, fiind folosita in cartografie, procesarea imaginilor, grafica pe calculator etc. Structura este un arbore ce reprezinta o zona din spatiul N-dimensional (in cazul in care suntem noi interesati, N=2), fiecare nod al arborelui pastreaza o informatie pentru o zona din spatiu, iar nodul are 2^N^ fii care reprezinta fiecare o zona de 2^N^ ori mai mica decat zona parintelui. Zonele fiilor sunt **disjuncte**, iar reuniunea lor formeaza zona parintelui.
_QuadTree_ este o structura care organizeaza informatii pentru date multidimensionale, fiind folosita in cartografie, procesarea imaginilor, grafica pe calculator etc. Structura este un arbore ce reprezinta o zona din spatiul N-dimensional (in cazul in care suntem noi interesati, $N=2$), fiecare nod al arborelui pastreaza o informatie pentru o zona din spatiu, iar nodul are $2^N^$ fii care reprezinta fiecare o zona de $2^N^$ ori mai mica decat zona parintelui. Zonele fiilor sunt **disjuncte**, iar reuniunea lor formeaza zona parintelui.
Pentru un _QuadTree_ radacina reprezinta un patrat, iar fii reprezinta cele patru patrate **disjuncte si congruente** in care se poate imparti patratul initial. Din cate am prezentat pana acum, un _QuadTree_ este infinit, dar pe noi ne intereseaza de obicei intervale foarte mici din plan, si atunci putem sa folosim numai cateva nivele din _QuadTree_. Cateodata unele noduri din _QuadTree_ nu contin insa nici o informatie si atunci nu avem nevoie sa le folosim pentru ca am folosi memorie in plus.
In +problema 3+ a zilei 2 a **Balcaniadei de Informatica** din 1997, se da un _QuadTree_ care reprezinta o imagine colorata alb-negru, de dimensiune 2^N^ * 2^N^. Daca patratul reprezentat de informatia dintr-un nod al arborelui era de aceeasi culoare, in nod se pastra informatia culorii si nodul nu avea nici un fiu, altfel nodul avea starea indecisa/nedeterminata si avea patru fii.
In +problema 3+ a zilei 2 a **Balcaniadei de Informatica** din 1997, se da un _QuadTree_ care reprezinta o imagine colorata alb-negru, de dimensiune $2^N^ * 2^N^$. Daca patratul reprezentat de informatia dintr-un nod al arborelui era de aceeasi culoare, in nod se pastra informatia culorii si nodul nu avea nici un fiu, altfel nodul avea starea indecisa/nedeterminata si avea patru fii.
!cautari-ortogonale?pic1.jpg!
!cautari-ortogonale?pic2.jpg!
!cautari-ortogonale?pic5.jpg!
!cautari-ortogonale?pic5.jpg!
Prima imagine prezinta ordinea in care fii reprezinta patratele, a doua imagine reprezinta o imagine alb-negru, iar a treia este reprezentarea sub forma de _QuadTree_ a acelei imagini.
Pentru a reprezenta $n$ puncte de coordonate intregi in plan cu ajutorul structurii de _QuadTree_, vom insera care un punct pe rand in _QuadTree_. Pornim de la un _QuadTree_ gol si inseram un nod recursiv, vedem pentru fiecare patrat care nu are latura de dimensiune unu in care din cele patru patrate din interiorul lui intra punctul nostru. Daca nu exista nod care sa reprezinte acel patrat, il creem noi.
Avantajul pentru structura de _QuadTree_ este usurinta implementarii, dezavantajul este ca structura lui si timpul de raspuns la intrebari depind si de configuratia punctelor, nu numai de numarul total de puncte.
