Triangulación de un polígono

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Una triangulación genérica de un polígono cóncavo

En geometría, la triangulación de un polígono o área poligonal es una partición de dicha área en un conjunto de triángulos por un conjunto máximal de diagonales que no se cruzan.[1]

Definición[editar]

De manera más precisa, una triangulación es una división del área en un conjunto de triángulos que cumplen las siguientes condiciones:

  • La unión de todos los triángulos es igual al polígono original.
  • Los vértices de los triángulos son vértices del polígono original.
  • Cualquier pareja de triángulos es disjunta o comparte únicamente un vértice o un lado.

La definición anterior es la estándar en geometría computacional aunque en ciertos contextos, al hablar de triangulaciones, se puede hacer caso omiso del segundo requisito. En tal caso, no se requiere que los vértices de los triángulos sean vértices del polígono y para referirse a las triangulaciones que sí satisfacen el requisito se habla de triangulaciones completas.[2] [3]

La partición de una superficie en triángulos se denomina también malla triangular en trigonometría y en geometría elemental. Y desde el punto de vista de la teoría de grafos, las triangulaciones son «grafos no orientados sin aristas múltiples», cuyos subgrafos son "círculos de tres nodos" (y correspondientemente tres aristas). Una generalización de las mallas triangulares son las mallas poligonales.

Propiedades de las triangulaciones de un polígono[editar]

Las 42 posibles triangulaciones para un heptágono. Este número viene dado por el número de Catalan.

A continuación se muestran propiedades de la triangulación de un polígono simple:

  • Todo polígono
  • Toda triangulación de un polígono simple con vértices consiste en exactamente triángulos.[1] [4]
  • Cada triangulación de un polígono simple de vértices usa diagonales.[1] [4]
  • Todo polígono convexo de vértices puede ser triangulado en abanico en triángulos, escogiendo un vértice y trazando todas las diagonales a vértices no vecinos.
  • De forma similar, todo polígono con un único vértice cóncavo puede ser triangulado en abanico en triángulos, escogiendo como origen el único vértice cóncavo y trazando las diagonales al resto de vértices.
  • La cantidad total de triangulaciones posibles de un polígono convexo de vértices es igual al ()-ésimo número de Catalan, es decir: , la demostración fue encontrada por Leonhard Euler.[5] [6]

Triangulaciones especiales[editar]

Ejemplos de triangulación de un polígono. 1. Abanico. 2. Mínimo peso 3. Delaunay
Triangulación voraz de un polígono ejecutada paso a paso.

Con frecuencia interesa calcular una triangulación que presente alguna propiedad especial, como por ejemplo evitar que algún triángulo tenga un área mayor de un umbral dado.

  • La Triangulación de Delaunay que, entre otras propiedades, maximiza el ángulo mínimo de los triángulos (evitando que aparezcan ángulos demasiado agudos).
  • La Triangulación voraz, que trata de emparejar los vértices más cercanos entre sí.
  • La Triangulación de peso mínimo (Minimum-weight Triangulation), que minimiza la suma total de longitudes de las aristas de los triángulos.
  • La Triangulación en abanico de un polígono convexo, eligiendo un vértice y trazando diagonales a los vértices no vecinos. Esta triangulación puede ser rápidamente calculada en tiempo lineal.

Un polígono monótono puede ser triangulado en tiempo lineal mediante alguno de los algoritmos siguientes:

Aplicaciones[editar]

Existen muchas aplicaciones que utilizan la triangulación de un polígono como uno de los pasos para la solución del problema. Por ejemplo:

  • Desde la antigüedad se ha utilizado para calcular el área de parcelas de terreno de forma irregular. El método más habitual es dividir la parcela en triángulos, cuyo cálculo de área es trivial conociendo la longitud de los lados, y sumar las áreas de los mismos. Posteriormente se desarrolló la llamada fórmula del agrimensor, para calcular áreas de terrenos y polígonos en general.
  • El problema de la galería de arte donde se resuelve el problema de visibilidad desde el mínimo número de puntos posible.
  • La deformación de superficies (especialmente tejidos) mediante el método de elementos finitos.

Generalización a dimensiones superiores[editar]

Descomposición de un cubo en 6 tetraedros, el simplejo de

La definición de triangulación puede ser fácilmente adaptada para elementos de dimensiones superiores. Así, se define una triangulación de un politopo en un espacio como un complejo simplicial formado por una colección de simplejos de tales que:

  • La unión de todos los simplejos es igual al politopo.
  • Los vértices de los simplejos son vértices del polítopo original.
  • Cualquier par de simplejos es disjunto o su intersección es exactamente alguna cara común.

Por ejemplo, en caso del espacio cualquier volumen encerrado en el interior de una superficie discreta cerrada, puede ser descompuesto en una serie de tetraedros (que es el simplejo de ). Esto tiene aplicaciones importantes como el cálculo de volúmenes de objetos complejos, o la deformación mediante el método de elementos finitos.

Referencias[editar]

  1. a b c de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark. Computational Geometry (3 edición). Springer. ISBN 978-3-540-77973-5. 
  2. Trias Pairó, Joan (2003). «3.9 Triangulación de polígonos simples». Geometría para la informática gráfica y CAD. Vol. 129 de Politext: Matemática y Estadística (1ª edición). Barcelona: Edicions UPC. p. 151. ISBN 9788483017029. Consultado el 25 de noviembre de 2011. 
  3. Hernández Cifre, María Ángeles y José Antonio Pastor González. «6.2.1 Triangulaciones. La característica de Euler-Poincaré». Un curso de geometría diferencial: teoría, problemas, soluciones y prácticas con ordenador. Vol. 47 de Textos universitarios, Consejo Superior de Investigaciones Científicas (España). España: CSIC, Ediciones Doce Calles. p. 232. ISBN 9788400091545. Consultado el 25 de noviembre de 2011. 
  4. a b O'Rourke, Joseph. Computational Geometry in C (2 edición). Cambridge University Press. ISBN 9780521649766. 
  5. Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
  6. Jesús D. Loera; Jörg Rambau; Francisco Santos (2010). Triangulations:Structures for Algorithms and Applicaciones. Algorithms and Computation in Mathematics (en inglés) 25. Springer. ISBN 9783642129704. 
  7. Fournier, A.; Montuno, D. Y. (1984), «Triangulating simple polygons and equivalent problems», ACM Transactions on Graphics 3 (2): 153-174, doi:10.1145/357337.357341, ISSN 0730-0301 
  8. Toussaint, Godfried T. (1984). «A new linear algorithm for triangulating monotone polygons». Pattern Recognition Letters 2 (3): 155-158. doi:10.1016/0167-8655(84)90039-4.