Triangulația Delaunay paralelă

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Triangulația unui set de puncte este o problemă foarte bine cunoscută și utilizată în multe domenii de cercetare științifică dar și în industria de entertainment (scanare 3D, algoritmi de găsire a căii optime în jocuri, etc). Putem rezuma problema triangulației unui set de puncte P în plan în găsirea unei organizări DT(P) astfel încât să nu existe niciun punct din P în circumcercul oricărui triunghi din DT(P). Triangulația Delauney este cea mai populară deoarece maximizează unghiul minim al tuturor triunghiurilor. Această triangulație este denumită după Boris Delaunay pentru munca depusa pe acest subiect din anul 1934.
Algoritmul Delaunay produce triunghiuri aproape echiunghiulare și poate fi calculat utilizând o complexitate de O(nlog(n)) (pentru cazul cel mai rău), unde n este numărul de puncte din mulțime.

Datorită popularității acestui algoritm, s-au încercat mai multe soluții paralele sau distribuite cu scopul de a mări viteza de triangulație. Versiunea paralelă cea mai întâlnită de triangulație Delauney este bazată pe metoda Divide et impera și apare în mod natural: problema este împărțită recursiv în subprobleme care apoi sunt rezolvate. Triangulația finală se obține unind toate rezultatele.
Problema esențială a acestei metode este că valorile de intrare devin din ce în ce mai mici la fiecare iterație și din acest motiv procesoarelor nu li se repartizează munca egal. Rezultatele practice sunt destul de slabe.[1]

Triangulația Delaunay incrementală[modificare | modificare sursă]

O triangulație T(P) a unui set de puncte P în spațiu Euclidian este o mulțime de arce E astfel încât:

  1. Nu există 2 arce care se intersectează într-un punct care nu este în P
  2. Arcele din E împart acoperitoarea convexă a lui P în triunghiuri

Triangulația DT(P) a unui set de puncte P din plan este de tip Delaunay dacă și numai dacă circumcercul oricărui triunghi din DT(P) nu conține alt punct din P în interior.

Deși algoritmul de inserție incrementală pentru triangulația Delaunay are complexitate O(n^2) în cazul cel mai rău și O(nlog(n)) în cazul cel mai des întâlnit, este foarte popular datorită simplității și robusteții. Punctele pot sa vină în orice moment al rulării aplicației și nu trebuie sa cunoaștem de la început numărul lor fiindcă sunt înserate câte unul pe rând. Însa trebuie sa cunoaștem de la început intervalele coordonatelor. De asemenea permite modificări în vederea obținerii triangulației cu constrângeri pentru metrici non-Euclidiene sau pentru triangulații 3D.

Algoritmul începe cu crearea unei învelitoare convexe sau crearea unui triunghi temporar ce cuprinde toate punctele înserate. A doua posibilitate pare sa fie mai bună fiindcă prima construcție adaugă nevoia de diferențiere a triunghiurilor de pe primul nivel în algoritmul de locație. Însă, folosirea triunghiului de început nu vine fără probleme. Acest triunghi temporar trebui scos la sfârșit și o alta problema este cum să alegem vârfurile lui. Poziția recomandată este (k,0), (0,k) și (-k,-k) unde K = 3 * mărimea cutiei învelitoare.
Pentru a insera un punct p_r, trebuie să localizam rapid triunghiul cu vârfurile p_u, p_j și p_k care conține punctul înserat. Acest triunghi se subdivide în alte 3 noi triunghiuri dacă punctul cade în triunghi și în 2 triunghiuri dacă acesta este pe un arc. În al doilea caz vecinul este împărțit cum apare în figura
Etape din Triangulația Delaunay
Însa după subdiviziune, unele triunghiuri care nu satisfac testul circumcercului, pot exista, în acest caz arcul greșit dintre doua triunghiuri este întors. Aceasta întoarcere poate face un alt triunghi sa nu satisfacă testul. Întoarcerea trebuie aplicată în mod repetat (este propagată în valuri până toate triunghiurile sunt corecte). Acest lucru înseamnă că inserția unui punct poate schimba toată triangulația.
Intoarcerea unui arc in triangulația Delaunay
Problema de bază este cum se poate găsi într-un mod eficient triunghiul care conține punctul. O posibilitate este să se folosească graful aciclic direcționat. Un graf aciclic direcționat este un arbore cu istoria inserțiilor. Fiecare nod din graf corespunde unui triunghi. Triunghiul curent valid este astfel în Frunze si cel mare de început este radacina. Localizarea punctului de inserție în aceasta structura de date poate fi făcută cu o complexitate de O(log(n)), cazul des întâlnit și O(n) cazul cel mai rău. Dacă ordinea inserțiilor este aleatoare, arborele este aproape balansat și probabilitatea cazului cel mai rău scade.[2]

Algoritmul triangulației aleatoare de tip Delauney incremental[modificare | modificare sursă]

  1. Început
    1. Inițializează triunghiul mare
    2. Calculează permutație aleatoare a punctelor p_0,p_1….p_ (n-1) din mulțimea P
    3. Pentru r = 0 pana la n-1 // incepe inserția
      1. Localizează triunghiul p_ip_jp_k aparținând lui DT(P) care conține p_r
      2. Dacă p_r aparține interiorului p_ip_jp_k
        1. Adaugă arc de la p_r la p_i , p_j, p_k si subdivide p_ip_jp_k in 3 triunghiuri
      3. Altfel
        1. Adaugă arc de la p_r la p_j și de la p_r la p_1, al treilea punct de la celalalt triunghi cu care se împarte p_i p_k si subdivizează 2 triunghiuri care împart p_i p_k în patru triunghiuri
        2. Legalizează triangulația (întorcând arcurile)
      4. Încheiere
      5. Ștergerea tuturor triunghiurilor care conțin puncte din triunghiul mare
  2. Încheiere


Paralelizare[modificare | modificare sursă]


Paralelizarea procesului de triangulație Delaunay nu este ușoară deoarece fiecare punct poate influenta drastic toată structura. Presupunem o arhitectura cu mai multe procesoare și o memorie partajată. Calculele vor fi partiționate între mai multe thread-uri. Un thread va funcționa de obicei pe un singur procesor. (Este posibil să pornească mai mult de un singur thread pe un procesor dar asta nu va îmbunătăți viteza). Deoarece fiecare thread funcționează pe aceeași structura de graf aciclic direcționat, trebuie implementată sincronizarea pe acesta. Sunt 3 metode prin care se poate sincroniza:

  1. Batch
  2. Pesimistă
  3. Optimistă

Metoda Batch[modificare | modificare sursă]


Putem modifica algoritmul serial după cum urmează: Avem mai multe thread-uri care localizează triunghiul în structura grafului care conțin punctul de intrare. Subdivizarea și legalizarea poate fi făcută de un thread specializat care primește un punct de intrare și un triunghi de la care se începe căutarea. Problema de baza este asigurarea comunicării între thread-ul specializat și cel de căutare. Aceasta poate fi rezolvată prin folosirea cozilor în memoria partajată. Dacă aceasta coada este goala thread-ul specializat trebuie sa aștepte. Întrebarea este cât de mare trebuie sa fie coada pentru a evita blocarea thread-urilor de căutare. Pe acest și sistem localizarea trebuie sa dureze mult mai mult decât subdivizarea și legalizarea deoarece în caz contrar, coada se va umple și performanta se va diminua. Din aceste motive, algoritmul Batch nu prea se implementează. [3][4]

Metoda pesimistă[modificare | modificare sursă]


Concluzia măsurătorilor algoritmului serial este aceea ca partea de localizare consuma în jur de 60% din timpul total necesar construirii triangulației.
Deși nu este suficient pentru metoda de batch, acest procent este suficient pentru cea pesimista. Metoda pesimista este o modificare a metodei batch. Nu exista thread specializat; toate thread-urile fac aceleași instrucțiuni. Atât timp cât sunt mai multe thread-uri care pot citi graful simultan, doar unul îl poate modifica. Thread-urile localizează ultimul triunghi părinte care conține punctual (citire) apoi intra într-o secțiune critica, termina localizarea, subdivide și legalizează (scriere) ieșind din secțiunea critica.
Fiecare nod din Graful aciclic include un marcator care marchează nodul ca în figură. Frunzele din graf sunt numite copii. Nodurile normale sunt noduri în care toți copii lor nu sunt Frunze. Nodurile ramase sunt marcate printr-o combinație de litere L,M și R. Litera L înseamna ca primul copil este frunza (nodul este ultimul părinte din stânga). Litera M înseamna că al doilea copil este frunza (ultimul părinte din mijloc) și în final litera R înseamnă că al treilea copil este frunza (ultimul părinte din dreapta).
Localizarea poate continua doar pe noduri normale, de exemplu în nodul MR putem testa triunghiul din stânga copilului, dar testarea triunghiurilor din mijloc sau dreapta poate fi făcuta doar în secțiunea critica( acestea sunt testate doar dacă punctul nu se afla în triunghiul din stânga)

Structura arbore în algoritmul Delaunay paralel

Metoda pesimista este simplă dar aduce un plus mic de viteza datorită secțiunii critice.

Thread principal[modificare | modificare sursă]

Input: O mulțime de puncte P = { p_i, I = 0,1,2… n-1} de n puncte în plan
Output: O triangulație Delaunay a lui P DT(P)

  1. Început
    1. Inițializează triunghiul mare
    2. Calculează o permutare random a lui (p_0), (p_1)(p_{n-1}) din P
    3. Subdivide P în m submulțimi un m este numărul de thread-uri
    4. Pornește toate thread-urile si așteaptă pana la finalizare
    5. Șterge toate thread-urile care conțin puncte din triunghiul mare
  2. Sfârșit

Thread Secundar[modificare | modificare sursă]

Input: O mulțime de puncte Pt = {(p_i), i= 0,1…n(m -1)} din plan Pt inclus in P
Output: Modifica DT(P)

  1. Începe
  2. Pentru r = 0 pana la n(m-1) // inserează p_r în DT(p)
    1. Începe localizarea în arborele aciclic direcționat pe nivelul frunzelor părinților ce conțin pr
    2. Dacă mai există vreun thread care lucrează cu Frunze așteptăm
    3. Intram în secțiunea critica
      1. Terminăm localizarea la nivelul frunzelor pentru triunghiul p_i p_j p_k din DT(P) ce conține p_r
      2. Subdivizam și cautăm triunghiuri noi
    4. Ieșim din secțiunea critică
  3. Sfârșit

Metoda Optimistă[modificare | modificare sursă]

Deși întoarcerile pot schimba toată triangulația, întoarcerea se poate face și local. Nu este nevoie sa blocăm toate frunzele grafului aciclic direcționat pentru un singur thread. Lăsam toate thread-urile sa facă localizarea, subdivizare și legalizare. Desigur ca trebuie să asiguram o sincronizare între toate thread-urile. Localizarea este aceeași cu cea din metoda pesimistă. În Nodul din graf se mai adaugă un marcator care spune ce thread blochează accesul la triunghi acesta este necesar pentru subdiviziune și legalizare. Thread-ul secundar blochează toate triunghiurile care sunt accesate și după ce punctul de intrare este inserat, toate triunghiurile blocate sunt deblocate. Dacă alt thread a blocat deja triunghiul, thread-ul curent trebuie să aștepte până se deblochează.

Exista o posibiltate de apariție a deadlock-urilor cauzate de așteptări simultane a thread-urilor. Aceasta problema se poate rezolva printr-un sistem de detecție a deadlock-urilor (thread-ul care detectează deadlock-ul se întoarce la partea de localizare și renunța la inserție pentru moment) sau prin prioritizarea thread-urilor (thread-ul nu este pus în așteptare pentru altul cu prioritate mai mare). Ambele posibilități conduc la utilizarea tranzacțiilor. Deoarece exista slabe șanse de deadlock-uri folosirea tranzacțiilor limitează îmbunatățirea vitezei.

Putem evita folosirea tranzacțiilor printr-o variație a metodei optimiste numita metoda hotului optimist. Aceasta metodă este ușor de înțeles: fiecare triunghi din obiect poate fi asociat cu un lucru. Fiecare lucru (Televizor, scaun, pat) are un proprietar (thread-ul). Lucrurile sunt stocate într-o casa care este a thread-ului (proprietarului). Presupunem ca toate lucrurile deținute de un thread sunt în casa acestuia. Planul este divizat în mai multe arii (case). Dacă un thread modifică triunghiuri doar din casa lui nu este nevoie sa folosim tranzacții sau sa blocam triunghiuri. Însa câteodată thread-ul trebuie să între în casa deținută de vecin. Din acest motiv trebuie să sune la ușa și să aștepte să se deschidă. Vecinul deschide ușa când și-a terminat treaba și din acest moment invitatul și gazda trebuie să blocheze triunghiurile.

Soluția nu este sigură din punct de vedere a deadlock-urilor deoarece este posibil ca 2 sau mai multe thread-uri să sune la ușă și să se aștepte. Situația aceasta se poate trata prin forțarea ușii (thread-ul care detectează problema intra și își face treaba) Când proprietarul casei realizează acesta trebuie să verifice la fiecare val de întorsuri că este permis să se schimbe obiectul fiindcă hoțul ar fi putut sa modifice triunghiuri neprocesate. Daca thread-ul nu poate continua în niciun val, counter-ul de problem potențiale este incrementat. Fiindcă știm fiecare triunghi care a fost produs de hoț, le putem marca pe acestea ca fiind greșite și le putem corecta la sfârșitul calculelor.

Thread secundar[modificare | modificare sursă]

Input: O mulțime de puncte Pt = { p_i, I = 0,1,n_m -1 } din n_m puncte din plan Pt inclus in P
Output: Modifica DT(P)

  1. Început
    1. Pentru r = 0 pana la n_m - 1 // inseram punctual pr in DT(p)
      1. Localizam in graf triunghiul p_i p_j p_k care conține p_r
      2. Cat timp triunghiul subdivizat și toți vecinii sunt blocați de cineva așteptăm;
      3. Blocăm triunghiul p_ip_jp_k și toți vecinii
      4. Cat timp triunghiurile legalizate și vecinii sunt blocați/blocate de cineva așteptăm;
      5. Blocăm triunghiurile legalizate si vecinii
      6. Legalizăm
      7. Deblocăm toate triunghiurile blocate de acest thread
      8. Trezim toate thread-urile care așteaptă după acesta;
    2. Sfârșit
  2. Sfârșit

Partiționarea mulțimii de puncte[modificare | modificare sursă]

Sunt doua metoda mari de partiționare a mulțimii de puncte în m submulțimi input pentru celelalte thread-uri

  1. Mulțimea de input este împărțit statistic. Acest lucru înseamnă că fiecare thread primește o parte din mulțime. Este o problemă în această partiționare fiindcă ultimul thread primește mai putin decât celelalte.
  2. Mulțimea de input nu este împărțită statistic dar fiecare thread înserează primul punct neinserat referit de un pointer global care este mărit în mod atomic. Aceasta se numește încărcătură dinamică.

Note[modificare | modificare sursă]

  1. ^ http://www.cescg.org/CESCG-2001/JKohout/index.html
  2. ^ http://www.cse.unsw.edu.au/~lambert/java/3d/delaunay.html
  3. ^ http://www.cs.cmu.edu/~quake/tripaper/triangle2.html
  4. ^ http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

Bibliografie[modificare | modificare sursă]

  • Blelloch, G.E., Miller, G.L., Talmor, D.: Developing a Practical projection-Based Parallel Delaunay algorithm, Proc of the 12th Annual Symposium on Comput. Geometry, ACM, 1996
  • de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry. Algorithms and Applications, Springer-Verlag Berlin Heidelberg, 1997
  • Guibas, L.J., Knuth, D.E., Sharir, M.: Randomized Incremental Construction of Delaunay and Voronoi Diagrams. Algorithmica (7), pp. 381-413, 1992
  • Hardwick, J.C.: Implementation and Evaluation of an Efficient Parallel Delaunay Triangulation Algorithm, 9th Annual Symposium on Parallel Algorithm and Architectures, pp. 22-25, 1997
  • Kolingerová, I., Kohout, J.: Pessimistic Threaded Delaunay Triangulation, GraphiCon'2000, pp. 76-83, 2000
  • Vigo, M.: An Improved Incremental Algorithm for Constructing Restricted Delaunay Triangulations, Computers & Graphics 21, pp. 215-223, 1997