Contents
1 Triangulaciónes
1.1 Algoritmo “Brute Force” – O(n³)
1.2 Metodo de otectomía – O(n²)
1.3 Triangluación de Delaunay
1.4 Triangulación del interior y exterior de un polígono
2 Aplicaciones de la triangluación
2.1 Triangular la región comprendida entre 2 polígonos PCQ
2.2 Problema de la galeria de arte: n/3 vértices vigilan el interior de un polígono
2.3 Polígono de visibilidad en O(n)
2.4 Operaciones booleanas en O(n²)
2.5 Rendering
2.6 Elementos finitos
3 Problemas
Triangulaciónes
Input: P=[v1,...,Vn] (lista de vertices)Output: Para la salida podrían haber varias opciones, una de ellas es sacar una lista de listas (lista de triángulos, o de diagonales que descompongan al polígono en triángulos).
Primeramente debemos tener en cuenta que para triangular no vale unir el centro del triangulo con los vértices. Además, si el polígono es convexo, bastaría con tomar uno de los vértice y unirlo con los demás vértices.
Un algoritmo para triangular es mediante diagonales. Para este caso, deberíamos obtener diagonales teniendo cuidado de que no se cortases entre ellas. Un algoritmo valido seria:
1 Si p es un triangulo, fin2 Hallar una diagonal d3 descomponer p en p1 y p2 mediante d4 Triangular P1 y P2
Otro algoritmo de triangulación seria:
Si la longitud de la lista inicial es igual a 3, se devuelve la lista de listas con los triángulos introduciendo los tres puntos restantes, fin. Si no, se toma la lista inicial con los tres primeros elementos y se mira si el segundo es convexo respecto del primero y tercero. Si lo es, miro si de todos los elementos de la primera lista hay alguno que está dentro del triangulo que forma los tres puntos tomados (área signada). De ser así, borro el primer elemento de la lista y lo inserto al final y repito el algoritmo. Si no, copio en una lista nueva los tres puntos y borro de la inicial el punto intermedio de los 3 tomados. Repito el algoritmo.
[ad#postcenter]
Algoritmo “Brute Force” – O(n³)
Metodo de otectomía – O(n²)
- Caso particular: Polígonos monótonos
Se deben tomar los puntos según la vertical. Si el 2º y tercero están en distinta cadena, pudo trazar una diagonal, si no, veo si los puntos están hacia fuera. Si dejamos puntos pendientes, se deben hacer retrocesos al obtener una nueva diagonal.
Para hacer un polígono monótono, puedo conectar el vértice cúspide con otro de arriba mediante una diagonal y así partir el polígono en 2 (siendo ya uno de ellos monótono).
Triangluación de Delaunay
- Si un polinomio está definido por cuatro vértices no es convexo, solo hay una triangulación posible. En cambio si es convexo, hay mas de una.
- ¿Cuáno una triangulación es buena?Una buena triangulación tenemos cuando el menor ángulo obtenido es el mayor posible. Para ver las posibles triangulaciones debemos “flipar”, es decir, realizar intercambios (to flip).En caso de que tengamos mas de cuatro puntos, se toma el mejor vector de ángulos.
- [α1,α2...α3n-6](numero total de ángulos) αi =< αi+1 (i=1 … 3n-7)(ángulos de los triángulos de T)
- La mejor solución será aquella cuyo vector de ángulos sea el mayor. Por ejemplo, dados T1 y T2, T2 será mejor T1 si [α1..α3n-6] =< [β1..β3n-6]
- Otra forma de ver cual es la mejor solución es a simple vista lógicamente geométrico. Si tomando un circulo que pase por los 3 puntos de un triangulo creado, el cuarto punto está fuera del circulo, esa sería la mejor opción.
[ad#postcenter]
Triangulación del interior y exterior de un polígono
- Para poder triangular por el exterior, el polígono tiene que ser no convexo ya que si no, hay diagonales externas. La triangulación de la parte externa se realiza como cualquier triangulación, pues lo que se triangula es un “bolsillo” o polígono.
Aplicaciones de la triangluación
Triangular la región comprendida entre 2 polígonos PCQ
- Una forma de resolver este problema sería haciendo fuerza bruta mediante test de intersección de segmentos, pero esta solución nos da una complejidad O(n³) a priori desechable.
- Otra forma sería triangular el triangulo externo O(nlogn), después ver cual es el vértice del triangulo interno que está mas a la derecha incluido en un triangulo que ha surgido de la triangulación ( O(nlogn) + O(n) = O(nlogn)), y hecho esto, le uno con el vértice mas a la derecha del triangulo exterior.
- Una tercera posible forma de resolución seria tomado el punto interno mas a la derecha, y el externo mas a la derecha (aunque valdría cualquiera del polígono externo). Hecho esto, miro si la diagonal creada es cortada por algún segmento, y de ser así, me quedo con el mas próximo al interno (de los dos anteriores). Tomo los vértices del segmento cortado y los uno con el punto interior. Si no corta ningún segmento o punto a las diagonales, termino, si no, repito la operación.
[ad#postcenter]
Problema de la galeria de arte: n/3 vértices vigilan el interior de un polígono
Este problema consiste en que dados n vértices de un triangulo, ¿cuantos vigilantes serán necesarios para los cuadros estén protegidos?
- La primera solución (pero mala) seria: Si se tienen n vértices, se necesitan n vigilantes, así la sala estaría perfectamente correcta. Pero esta solución no es nada buena.
- La segunda y mejora solución sería: Se triangula el polígono dado, y se numeran los vértices de cada triangulo de la manera que el vértice que forma un triangulo y su/sus adyacentes tengan el mismo numero. De esta manera se puede asegurar que con n/3 de vigilantes, la galería estará protegida. Se podría dar también el caso de que necesitásemos menos vigilantes de n/3.