Triangularea unui poligon

Triangularea unui poligon

În Format:Ill-wd triangularea unui poligon este împărțirea suprafeței unei zone poligonale (poligon simplu) Format:Mvar în un set de triunghiuri, adică găsirea unui set de triunghiuri cu interioare neintersectate în perechi, a căror reuniune este Format:Mvar.

Triangulările pot fi privite ca fiind cazuri speciale de grafuri planare cu muchii drepte. Când nu există găuri sau puncte adăugate, triangulările formează un Format:Ill-wd.

Triangularea poligonului fără vârfuri adiționale

În decursul timpului au fost propuși o serie de algoritmi pentru a triangula un poligon.

Cazuri particulare

Cele 42 de triangulări posibile pentru un heptagon convex (poligon convex cu 7 laturi). Acest număr este dat de al 5-lea număr Catalan.

Triangularea oricărui poligon convex în timp liniar printr-o triangulare în evantai, prin adăugarea de diagonale de la un vârf la toate celelalte vârfuri care nu sunt vecine cu cel inițial, este trivială.

Numărul total de moduri de a triangula un n-gon convex prin diagonale care nu se intersectează este al (n−2)-lea număr Catalan, care este egal cu

$\frac{n(n+1)...(2n-4)}{(n-2)!}$,

formulă găsită de Leonhard Euler.

Un poligon monoton poate fi triangulat în timp liniar fie cu algoritmul lui Alain Fournier și D.Y. Montuno, fie cu algoritmul lui Godfried Toussaint.

Metoda tăierii urechii

Urechea unui poligon

O metodă de a triangula un poligon simplu se bazează pe teorema celor două urechi, deoarece orice poligon simplu cu cel puțin 4 vârfuri și fără găuri are cel puțin două „urechi, care sunt triunghiuri cu două laturi pe laturile poligonului și a treia aflându-se complet în interiorul acestuia. Algoritmul constă în găsirea unei astfel de urechi, separarea acesteia din poligon (rezultă un nou poligon care încă îndeplinește condițiile) și repetarea până când rămâne un singur triunghi.

Acest algoritm este ușor de implementat, dar mai lent decât alți algoritmi și funcționează numai la poligoane fără găuri. O implementare care păstrează liste separate de vârfuri convexe și concave va rula în timp Format:Math. Această metodă este cunoscută sub denumirea de tăierea urechilor. Un algoritm eficient pentru tăierea urechilor a fost descoperit de Hossam ElGindy, Hazel Everett și Godfried Toussaint.

Triangularea unui poligon monoton

Împărțirea unui poligon în poligoane monotone

Un poligon simplu este monoton în raport cu o dreaptă Format:Mvar, dacă vreo dreaptă ortogonală pe Format:Mvar intersectează poligonul de cel mult două ori. Un poligon monoton poate fi împărțit în două lanțuri monotone. Un poligon care este monoton în raport cu axa Format:Mvar se numește monoton față de Format:Mvar. Un poligon monoton cu Format:Mvar vârfuri poate fi triangulat în timp Format:Math. Presupunând că un poligon dat este monoton față de Format:Mvar, algoritmul greedy începe prin a merge pe un lanț al poligonului de sus în jos în timp ce adaugă diagonale ori de câte ori este posibil. Este ușor de observat că algoritmul poate fi aplicat oricărui poligon monoton.

Triangularea unui poligon care nu este monoton

Dacă un poligon nu este monoton, acesta poate fi împărțit în subpoligoane monotone în timp Format:Math folosind un algoritm de baleiere (în Format:En). Algoritmul nu necesită ca poligonul să fie simplu, astfel că poate fi aplicat poligoanelor cu găuri. În general, acest algoritm poate triangula o subdiviziune plană cu Format:Mvar vârfuri în timp Format:Math folosind Format:Math spațiu.

Graful dual al triangulării

Un graf util care este adesea asociat cu o triangulare a unui poligon Format:Mvar este graful dual. Având în vedere o triangulare Format:Mvar a Format:Mvar, se definește graful Format:Mvar(Format:Mvar) ca graf al cărui set de noduri sunt triunghiurile lui Format:Mvar, două vârfuri (triunghiuri) fiind adiacente dacă și numai dacă au în comun o diagonală. Este ușor de observat că Format:Mvar(Format:Mvar) este un arbore cu gradul maxim 3.

Complexitate de calcul

Până în 1988 în geometria algoritmică era o problemă deschisă dacă un poligon simplu poate fi triangulat mai repede decât în timp Format:Math. Apoi, Tarjan Van Wyk a descoperit un algoritm de triangulare în timp Format:Math, ulterior simplificat de Kirkpatrick, Klawe și Tarjan. Au urmat o serie de metode îmbunătățite, cu complexitatea Format:Math, în practică nedistingându-se de complexitatea în timp liniar.

Bernard Chazelle a arătat în 1991 că orice poligon simplu poate fi triangulat în timp liniar, însă algoritmul propus este foarte complex. Se cunoaște și un algoritm mai simplu, de la care se așteaptă un timp liniar. Algoritmul de descompunere al lui Seidel și metoda de triangulare a lui Chazelle sunt discutate în detaliu de Li și Klette.

Complexitatea în timp a triangulării unui poligon cu n vârfuri cu găuri în modele modelele de calcul ale arborelui de calcul are limită inferioară Format:Math. Este posibil să se calculeze numărul de triangulări distincte ale unui poligon simplu în timp polinomial folosind Format:Ill-wd și (pe baza acestui algoritm de numărare) să se genereze triangulări uniform aleatoare în timp polinomial. Totuși, numărarea triangulărilor unui poligon cu găuri este P-completă, ceea ce face puțin probabil să se poată face în timp polinomial.

Legături externe

• Format:En icon Demo as Flash swf, A Sweep Line algorithm.
• Format:En icon Song Ho's explanation of the OpenGL GLU tesselator