Triangulating Non Convex Polygons

[Zaelsius]

 Debo de estar algo aturdido por los exámenes, pq sigo sin ver la conexión ¿?

Se supone que el algoritmo de pathfinding buscaba una ruta alrededor de tríangulos.. ¿? dont get it  

[MChiz]

 Ahora no me voy a poner a explicarlo... espero que me entiendas : )
Pero vendria a ser mas o menos lo que dices, pero en vez de triangulos, zonas convexas ( y digo convexo, no concavo )

[Zaelsius]

 Vale, ya entiendo lo que dices... :P  

[MChiz]

 Me alegro : )

[TurMach]

 Esto es interesante:

triangular un poligono es facil, al reves NO. Por facil me refiero computacionalmente.

Para triangular un poligono debes dividirlo recursivamente mediante "diagonales internas". Una diagonal interna es un segmento entre dos vertices no consecutivos que no se cruza con otro segmento. Al dividir un poligono con una diagonal interna te quedan dos poligonos que se van a dividir de nuevo; asi hasta llegar a un triangulo simple.

Crear un poligono CONCAVO a partir de un conjunto de triangulos es trivial y no se me ocurre para que puede servir.

Pero para formar un conjunto de poligonos CONVEXOS a partir de un conjunto de triangulos no se ningun algoritmo eficiente. Se podria construir un modelo de fronteras y formar subconjuntos de triangulos de manera sistematica ( N contra N ) y realizar un test de convexidad para cada uno. Pero te queda el problema de saber si es la solucion mas eficiente, ya que hay multiples soluciones. Se parace al problema de crear strips a partir de un conjunto de triangulos.

:)  

[MChiz]

 Ei TurMach! Cuanto tiempo!! ; )
Te acuerdas de mis ralladas con el tema? jejejeje ai la leche, que dificil es la vida del programador ;bb