Platformă de e-learning și curriculă e-contentpentru învățământul superior tehnic
Geometrie computationala
6. Triangularea poligoanelor simple. Teoria triangularii. Algoritmi de triangulare
Triangularea poligoanelor simple• Intrare: un poligon simplu P descris de un sir ordonat de varfuri
<v0, …vn–1>.
• Poligon simplu: lant poligonal inchis non-intersectabil
• Iesire: o partitionare a lui P in n-2 triunghiuri nesuprapuse, siadiacentele dintre ele.
Exemple de triangulare
Istoric al algoritmilor
• O(nlogn) Monotone pieces 1978• O(nlogn) D&C 1982• O(nlogn) Plane Sweep 1985• O(nlog*n) Randomized 1991• O(n) Polygon cutting, 1991• O(n) Randomized 2000• O(n) folosind constante mici ??
Observatii
• Triangularea nu este unica. O varianta de triangulare este suficienta.
• Triangularea este posibila in orice situatie.
• Nu sunt necesare varfuri suplimentare.
• Triangularea adauga noi muchii, numitediagonale, intre varfurile existente.
Teoria triangularii (1)
• Un varf este convex daca unghiul sau interior este < π, in cazcontrar acesta este concav.
• O diagonala este o noua muchie intre doua varfuri ale unuipoligon si se afla complet inclusa in poligon.
• Lema 1: Orice poligon are un varf convex.
• Demonstratie: Varful care are coordonata y cea mai mare este convex.
Nu orice segment intre doua
varfuri este diagonala
Teoria triangularii (2)Lema 2: Orice poligon cu n > 3
varfuri are o diagonala.
Demonstratie: fie v un varfconvex si a, b, varfurile saleadiacente. Deoarece P este unpoligon simplu si n > 3, nuexista o muchie intre a si b.
Se considera urmatoarele douacazuri:
1. Noua muchie ab este o diagonala
2. In caz contrar, exista un varf xce este cel mai apropiat de vraportat la o linie L paralela cu ab, care este o diagonala.
a
b
v
Cazul 1
b
a
v
xL
Cazul 2
Teoria triangularii (3)Teorema: Orice poligon planar simplu cu n muchii are o triangulare
in n-2 triunghiuri folosind n-3 diagonale
Demonstratie (inductie):• Baza: Un triunghi (n=3) are o triangulare fara diagonale si un
singur triunghi rezultant.
P1
P2v
• Inductie pe n:
• Pentru un poligon cu n varfuri
se construieste o diagonala ce
imparte poligonul in doua
poligoane P1 si P2 cu n1 si n2
varfuri astfel incat n1+n2–2 = n.
Diagonale: (n1–3)+(n2 –3)+1 = (n1+n2–2)–3 = n–3
Triunghiuri: (n1–2)+(n2–2) = (n1+n2–2)–2 = n–2
Duala triangulariiDefinitie: Duala unei triangulari T a unui
poligon simplu P este un graf unde:
Varfurile sunt triunghiuri din T
Muchiile reprezinta adiacente intre triunghiuri
Proprietate: duala triangularii este un arbore in
care gradul oricarui nod este maxim 3.
Demonstratie:
Grad ≤ 3 (din constructie). Nici un triunghi nu are mai mult
de 3 vecini.
Lipsa cicluri (prin contradictie). Daca ar exista un ciclu, nu
ar mai fi poligon simplu (are avea gauri).
De fapt, T este un arbore binar!
Algoritm simplu de triangulare (1)Idee: Se reduce poligonul prin
taierea unui triunghi lafiecare iteratie.Triunghiul taiat va fi formatdin 3 varfuri consecutive(vi,vi+1,vi+2). Diagonala este(vi,vi+2).
Test de validitate:1. Diagonala nu intersecteaza
alte varfuri ale poligonului.2. Diagonala trebuie sa fie in
interiorul poligonului.
Algoritm simplu de triangulare (2)proc trianguleaza(P)
if |P| ≤ 3
intoarce(P);
return;
i0;
while diagonala(vi,vi+2) nu este legala
i++;
intoarce(vi,vi+1,vi+2);
elimina vi+1 din P;
trianguleaza(P);
Complexitate: n × n teste ale diagonalelor, fiecare avand un cost de O(n) O(n3).
Surse ale ineficientei:
▫ Teste repetate ale diagonalelor
▫ Diagonalele nu sunt sortate sau ordonate
▫ Diagonalele pot fi precalculate in O(n2).
v1
v0
v2
Triangularea in O(nlogn)
1. Se partitioneaza poligonul in componente monotone.
2. Se trianguleaza fiecare componenta monotona separat.