Triangularea unui poligon

În geometria algoritmică^⁠(d) triangularea unui poligon este împărțirea suprafeței unei zone poligonale (poligon simplu) $P$ în un set de triunghiuri,^[1]^[2] adică găsirea unui set de triunghiuri cu interioare neintersectate în perechi, a căror reuniune este $P$ .

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 graf planar exterior^⁠(d).

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.^[3]

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

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.^[6] 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 $O(n 2)$ . 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.^[7]

Triangularea unui poligon monoton

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

Un poligon simplu este monoton în raport cu o dreaptă $L$ , dacă vreo dreaptă ortogonală pe $L$ 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 $y$ se numește monoton față de $y$ . Un poligon monoton cu $n$ vârfuri poate fi triangulat în timp $O(n)$ . Presupunând că un poligon dat este monoton față de $y$ , 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.^[2] 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 $O(n log n)$ folosind un algoritm de baleiere (în engleză sweep). 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 $n$ vârfuri în timp $O(n log n)$ folosind $O(n)$ spațiu.^[2]

Graful dual al triangulării

Un graf util care este adesea asociat cu o triangulare a unui poligon $P$ este graful dual. Având în vedere o triangulare $T P$ a $P$ , se definește graful $G$ ( $T P$ ) ca graf al cărui set de noduri sunt triunghiurile lui $T P$ , două vârfuri (triunghiuri) fiind adiacente dacă și numai dacă au în comun o diagonală. Este ușor de observat că $G$ ( $T P$ ) 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 $O(n log n)$ . Apoi, Tarjan Van Wyk a descoperit un algoritm de triangulare în timp $O(n log log n)$ ,^[8] ulterior simplificat de Kirkpatrick, Klawe și Tarjan.^[9] Au urmat o serie de metode îmbunătățite, cu complexitatea $O(n log * n)$ , în practică nedistingându-se de complexitatea în timp liniar.^[10]^[11]^[12]

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

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ă $Ω(n log n)$ .^[2] Este posibil să se calculeze numărul de triangulări distincte ale unui poligon simplu în timp polinomial folosind programarea dinamică^⁠(d) și (pe baza acestui algoritm de numărare) să se genereze triangulări uniform aleatoare în timp polinomial.^[16] 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.^[17]

Note

^ „triangulare” la DEX online
^ ^a ^b ^c ^d en de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), „3: Polygon Triangulation”, Computational Geometry (ed. 2nd), Springer-Verlag, pp. 45–61, ISBN 3-540-65620-0
^ en Pickover, Clifford A. (2009), The Math Book, Sterling, p. 184
^ en Fournier, Alain; Montuno, Delfin Y. (1984), „Triangulating simple polygons and equivalent problems”, ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301
^ en Toussaint, Godfried T. (1984), „A new linear algorithm for triangulating monotone polygons”, Pattern Recognition Letters, 2 (3): 155–158, Bibcode:1984PaReL...2..155T, doi:10.1016/0167-8655(84)90039-4
^ en Meisters, Gary Hosler (1975), „Polygons have ears”, American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703
^ en ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993), „Slicing an ear using prune-and-search”, Pattern Recognition Letters, 14 (9): 719–722, Bibcode:1993PaReL..14..719E, doi:10.1016/0167-8655(93)90141-y
^ en Tarjan, Robert E.; Van Wyk, Christopher J. (1988), „An O(n log log n)-time algorithm for triangulating a simple polygon”, SIAM Journal on Computing, 17 (1): 143–178, CiteSeerX 10.1.1.186.5949  , doi:10.1137/0217010, MR 0925194
^ en Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), „Polygon triangulation in O(n log log n) time with simple data structures”, Discrete & Computational Geometry, 7 (4): 329–346, doi:10.1007/BF02187846  , MR 1148949
^ en Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), „A fast Las Vegas algorithm for triangulating a simple polygon”, Discrete & Computational Geometry, 4 (5): 423–432, doi:10.1007/BF02187741 
^ en Seidel, Raimund (1991), „A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons”, Computational Geometry, 1: 51–64, doi:10.1016/0925-7721(91)90012-4 
^ en Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), „Randomized parallel algorithms for trapezoidal diagrams”, International Journal of Computational Geometry & Applications, 2 (2): 117–133, doi:10.1142/S0218195992000081, MR 1168952
^ en Chazelle, Bernard (1991), „Triangulating a Simple Polygon in Linear Time”, Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703  , ISSN 0179-5376
^ en Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), „A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time”, Discrete & Computational Geometry, 26 (2): 245–265, doi:10.1007/s00454-001-0027-x  , ISSN 0179-5376, arhivat din original la 23 iulie 2018, accesat în 8 ianuarie 2023
^ en Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5
^ en Epstein, Peter; Sack, Jörg-Rüdiger (1994), „Generating triangulations at random”, ACM Transactions on Modeling and Computer Simulation, 4 (3): 267–278, doi:10.1145/189443.189446
^ en Eppstein, David (2019), „Counting polygon triangulations is hard”, Proc. 35nd Int. Symp. Computational Geometry, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl, pp. 33:1–33:17, arXiv:1903.04737  , doi:10.4230/LIPIcs.SoCG.2019.33

Legături externe

Portal Matematică

en Demo as Flash swf, A Sweep Line algorithm.
en Song Ho's explanation of the OpenGL GLU tesselator

[1] „triangulare” la DEX online

[bkos-2] ^ ^a ^b ^c ^d en de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), „3: Polygon Triangulation”, Computational Geometry (ed. 2nd), Springer-Verlag, pp. 45–61, ISBN 3-540-65620-0

[3] Pickover, Clifford A. (2009), The Math Book, Sterling, p. 184

[4] Fournier, Alain; Montuno, Delfin Y. (1984), „Triangulating simple polygons and equivalent problems”, ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301

[5] Toussaint, Godfried T. (1984), „A new linear algorithm for triangulating monotone polygons”, Pattern Recognition Letters, 2 (3): 155–158, Bibcode:1984PaReL...2..155T, doi:10.1016/0167-8655(84)90039-4

[6] Meisters, Gary Hosler (1975), „Polygons have ears”, American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703

[7] ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993), „Slicing an ear using prune-and-search”, Pattern Recognition Letters, 14 (9): 719–722, Bibcode:1993PaReL..14..719E, doi:10.1016/0167-8655(93)90141-y

[8] Tarjan, Robert E.; Van Wyk, Christopher J. (1988), „An O(n log log n)-time algorithm for triangulating a simple polygon”, SIAM Journal on Computing, 17 (1): 143–178, CiteSeerX 10.1.1.186.5949  , doi:10.1137/0217010, MR 0925194

[9] Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), „Polygon triangulation in O(n log log n) time with simple data structures”, Discrete & Computational Geometry, 7 (4): 329–346, doi:10.1007/BF02187846  , MR 1148949

[10] Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), „A fast Las Vegas algorithm for triangulating a simple polygon”, Discrete & Computational Geometry, 4 (5): 423–432, doi:10.1007/BF02187741 

[11] Seidel, Raimund (1991), „A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons”, Computational Geometry, 1: 51–64, doi:10.1016/0925-7721(91)90012-4 

[12] Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), „Randomized parallel algorithms for trapezoidal diagrams”, International Journal of Computational Geometry & Applications, 2 (2): 117–133, doi:10.1142/S0218195992000081, MR 1168952

[13] Chazelle, Bernard (1991), „Triangulating a Simple Polygon in Linear Time”, Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703  , ISSN 0179-5376

[14] Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), „A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time”, Discrete & Computational Geometry, 26 (2): 245–265, doi:10.1007/s00454-001-0027-x  , ISSN 0179-5376, arhivat din original la 23 iulie 2018, accesat în 8 ianuarie 2023

[15] Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5

[16] Epstein, Peter; Sack, Jörg-Rüdiger (1994), „Generating triangulations at random”, ACM Transactions on Modeling and Computer Simulation, 4 (3): 267–278, doi:10.1145/189443.189446

[17] Eppstein, David (2019), „Counting polygon triangulations is hard”, Proc. 35nd Int. Symp. Computational Geometry, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl, pp. 33:1–33:17, arXiv:1903.04737  , doi:10.4230/LIPIcs.SoCG.2019.33

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]