Triangulació d'un polígon

Per a atres usos d'este terme vore Triangulació (desambiguación).

En geometria, la triangulació d'un polígon o àrea poligonal és una partició de dita àrea en un conjunt de triànguls per un conjunt máximal de diagonals que no es creuen.^[1]

Definició

De manera més precisa, una triangulació és una divisió de l'àrea en un conjunt de triànguls que complixen les següents condicions:

L'unió de tots els triànguls és igual al polígon original.
Els vèrtiços dels triànguls són vèrtiços del polígon original.
Qualsevol parella de triànguls és disjunta o compartix únicament un vèrtiç o un costat.

La definició anterior és l'estàndar en geometria computacional encara que en certs contexts, en parlar de triangulacions, es pot fer cas omís del segon requisit. En tal cas, no es requerix que els vèrtiços dels triànguls siguen vèrtiços del polígon i per a referir-se a les triangulacions que sí satisfan el requisit es parla de triangulacions completes.^[2]^[3]

La partició d'una superfície en triànguls es denomina també malla triangular en trigonometria i en geometria elemental. I des del punt de vista de la teoria de grafos, les triangulacions són «grafos no orientats sense arestes múltiples», que els seus subgrafos són "círculs de tres nodos" (i correspondientemente tres arestes). Una generalisació de les malles triangulars són les malles poligonales.

Propietats de les triangulacions d'un polígon

A continuació es mostren propietats de la triangulació d'un polígon simple:

Tot polígon simple admet sempre a lo manco una triangulació.
Tota triangulació d'un polígon simple en $n$ vèrtiços consistix en exactament $n - 2$ triànguls.^[1]^[4]
Cada triangulació d'un polígon simple de $n$ vèrtiços usa $n - 3$ diagonals.^[1]^[4]

Tot polígon convexo de $n$ vèrtiços pot ser triangulado en palmito en $n - 2$ triànguls, triant un vèrtiç i traçant totes les diagonals a vèrtiços no veïns.
De forma similar, tot polígon en un únic vèrtiç cóncau pot ser triangulado en palmito en $n - 2$ triànguls, triant com a orige l'únic vèrtiç cóncau i traçant les diagonals al restant de vèrtiços.
La cantitat total de triangulacions possibles d'un polígon convexo de $n$ vèrtiços és igual al ( $n - 2$ )-ésimo número de Catalan, és dir: $t_{n} = C_{n - 2} = \frac{1}{n - 1} (\binom{2 n - 4}{n - 2})$ , la demostració va ser trobada per Leonhard Euler,^[5]^[6] i es basa en fer una biyección entre triangulacions d'un polígon de $n$ costats i arbres binarios de $n - 1$ fulls posant la raïl d'estos en el triàngul d'un costat prefixat del polígon, un nodo en cada atre triàngul, i branques entre nodos de triànguls contigus. Com d'arbres binarios hi ha $C_{n - 2}$ i hi ha una biyección en les triangulacions, hi ha la mateixa cantitat d'estes últimes.

Referències

↑ ^1,0 ^1,1 ^1,2 Computational Geometry, 3 edició, Springer. ISBN 978-3-540-77973-5.
↑ Trias Pairó (2003). «3.9 Triangulació de polígons simples», Geometria per a l'informàtica gràfica i CAD, 1ª edició, Barcelona: Edicions UPC, p. 151. ISBN 8483017024, 9788483017029.
↑ Hernández Sifre, María Àngels i José Antonio Pastor González. «6.2.1 Triangulacions. La característica de Euler-Poincaré», Un curs de geometria diferencial: teoria, problemes, solucions i pràctiques en ordenador, Espanya: CSIC, Edicions Dotze Calles, p. 232. ISBN 840009154X, 9788400091545.
↑ ^4,0 ^4,1 Computational Geometry in C, 2 edició, Cambridge University Press. ISBN 9780521649766.
↑ Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
↑ Jesús D. Loera (2010). Triangulations:Structures for Algorithms and Applicaciones (en anglés), Springer. ISBN 9783642129704.

Referències

Este artícul conté una traducció derivada de «Triangulación de un polígono» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[deBerg-1] 1,0 ^1,1 ^1,2 Computational Geometry, 3 edició, Springer. ISBN 978-3-540-77973-5.

[2] Trias Pairó (2003). «3.9 Triangulació de polígons simples», Geometria per a l'informàtica gràfica i CAD, 1ª edició, Barcelona: Edicions UPC, p. 151. ISBN 8483017024, 9788483017029.

[3] Hernández Sifre, María Àngels i José Antonio Pastor González. «6.2.1 Triangulacions. La característica de Euler-Poincaré», Un curs de geometria diferencial: teoria, problemes, solucions i pràctiques en ordenador, Espanya: CSIC, Edicions Dotze Calles, p. 232. ISBN 840009154X, 9788400091545.

[Rourke-4] 4,0 ^4,1 Computational Geometry in C, 2 edició, Cambridge University Press. ISBN 9780521649766.

[5] Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.

[Loera2010-6] Jesús D. Loera (2010). Triangulations:Structures for Algorithms and Applicaciones (en anglés), Springer. ISBN 9783642129704.

[1]

[2]

[3]

[4]

[5]

[6]