En geometría algorítmica , la triangulación de un polígono consiste en descomponer este polígono en un conjunto (finito) de triángulos .
Una triangulación de un polígono P es una partición P en una pluralidad de triángulos que no se superponen, y cuya unión es P . En el caso más restrictivo, se impone que los vértices de los triángulos que son los vértices de P . En un marco más permisivo, podemos agregar vértices dentro de P o en el borde para que sirvan como vértices para los triángulos.
Las triangulaciones son casos especiales de gráficos planos rectilíneos ( es decir, cuyas aristas son segmentos).
La triangulación de un polígono convexo es trivial y se calcula en tiempo lineal, por ejemplo, comenzando desde un vértice y agregando aristas con todos los demás vértices. En 1991, Bernard Chazelle demostró que cualquier polígono simple se puede triangular en tiempo lineal. Sin embargo, el algoritmo propuesto es muy complejo y siempre se buscan algoritmos más simples.
Una forma de triangular un polígono simple es usar el hecho de que cualquier polígono simple con al menos cuatro vértices tiene al menos dos "orejas". Una oreja es un triángulo con dos aristas pertenecientes al borde del polígono y la tercera ubicada dentro del polígono. El algoritmo consiste en encontrar dicha oreja, sacarla del polígono, dando como resultado un nuevo polígono que aún cumple con las condiciones, y repetir la operación hasta que solo quede un triángulo.
Este algoritmo es simple de implementar, pero subóptimo: una implementación que almacena listas separadas de vértices para los triángulos y el polígono tendrá complejidad en O ( n 2 ).
Un polígono monótono (in) es tal que su borde se puede dividir en dos partes, cada una de las cuales está formada por puntos cuyas coordenadas según una determinada dimensión solo aumentan: el borde no retrocede "atrás". Fournier (en) y Montuno han demostrado que tal polígono se puede triangular en tiempo lineal.
Para dividir un polígono en polígonos monótonos, usamos una línea vertical u horizontal que barre las coordenadas en una dirección.
Este algoritmo tiene una complejidad en O ( n log n ).