una teselados teselaciones tesela sirven regulares que para matematicas los faciles escher colorear animales algorithm language-agnostic topology graphics tesselation

algorithm - teselados - Teselar un polígono arbitrario mediante mosaicos de mosaico



teselados para colorear (4)

Necesito llenar un polígono arbitrario usando un mosaico casi uniforme de triángulos. ¿Cómo haría esto? Puede proporcionar referencias a algoritmos existentes o incluso simplemente ideas o sugerencias propias.

Se presume lo siguiente:

  • El polígono puede ser convexo (pero puntos de bonificación si se obtiene un algoritmo que funciona para formas cóncavas)
  • El polígono tiene un número arbitrario de bordes (3 o más)
  • La cantidad de teselado (preferiblemente la cantidad de vértices añadidos por el algoritmo) debe parametrizarse
  • Los bordes del polígono se pueden dividir por el algoritmo
  • Los triángulos deben ser casi uniformes en tamaño y forma (es decir, las esquinas tenderán hacia 60 grados)
  • Preferiblemente, los bordes numéricos en un vértice deberían ser pocos en lugar de muchos. Esto probablemente seguirá del punto anterior (es decir, el algoritmo debería producir una "malla limpia").

Este no es un problema fácil de resolver y espero que una solución "heurística" sea la más eficiente ... (¿verdad?)

Como Jason Orendorff señaló, deberías tratar de usar Triangle para generar una malla de calidad. Tiene muchas opciones con las que puedes jugar para tratar de obtener una malla isotrópica. Entonces, podrías tratar de usar un algoritmo iterativo para crear una triangulación bien centrada. Más detalles se enumeran en esta página de publicaciones . Implementé el documento de 2007 "Triangulación planar bien centrada: un enfoque iterativo" y arroja resultados decentes en mallas de tamaño medio. Una triangulación bien centrada es aquella en la que todos los circuncentros de triángulos se encuentran dentro del triángulo respectivo. Como desea algo ligeramente diferente, simplemente podría intentar cambiar la métrica de error involucrada. Puede encontrar una medida de "no congruencia" entre los triángulos y minimizar ese error. Lo más probable es que dicha función de error no sea convexa, por lo que la optimización de gradiente conjugado no lineal descrita es tan buena como puede hacerlo.

Triangle hace lo que quieres?

(Las explicaciones de los algoritmos en ese sitio son mejores que cualquier cosa que se me ocurra).

Esto se puede hacer para polígonos cóncavos / convexos usando un método de recorte de oreja simple (asumiendo que no necesitamos soportar agujeros).

Esto es en 2 pasos, por lo que puede ser más eficiente recortar iterativamente el "mejor" oído para obtener resultados más parejos, por lo que no es necesario volver a organizar la topología como un segundo pase (YMMV).
(Tenga en cuenta que las razones por las cuales se usan 2 pasos aquí es que no siempre es necesario calcular una distribución más pareja).

La revelación completa, me encontré con este problema, cuando necesitaba un tessellator rápido para polígonos para una aplicación de modelado en tiempo real.

Implementación de trabajo escrita en C,
que toman y devuelven POD''s ( float[2] array, completando un uint[3] array):

(Tenga en cuenta que el recorte de orejas se basa en libgdx con optimizaciones espaciales para las comprobaciones de intersección, para escalar hasta miles de lados sin un golpe de rendimiento tan significativo, ya que cortar cada oreja fue revisar todos los demás puntos cada vez).

En realidad, no suena tan complicado, algorítmicamente. ¿O me estoy perdiendo algo?

Algunos pseudocódigo:

  • Coloque un cuadrado delimitador alineado al eje alrededor de su polígono.
  • Subdividir cada cuadro en cuatro elementos (similar a un árbol cuádruple), donde el número de iteraciones determina su "cantidad de teselado".
  • Cada cuadrado resultante está limpiamente fuera de su polígono (= ignorar), limpiamente dentro de su polígono (= dividido en dos triángulos de teselación resultante a lo largo de la diagonal) o interseca su polígono.
  • Los casos exactos para los cuadrados de intersección se dejan como un ejercicio para el lector. ;-) [En este punto en el tiempo, al menos.]

Sin embargo, le dará triángulos con ángulos de 45 ° / 45 ° / 90 °. Si desea acercarse lo más posible a 60 °, comience con teselando la superficie de su polígono con hexágonos (con el tamaño del hexágono como su "cantidad de teselado") y luego revisando cada uno de los seis 60 ° / 60 ° / Triángulos de 60 ° que componen estos hexágonos. Para estos triángulos haces lo mismo que con los cuadrados en el pseudocódigo anterior, excepto por el hecho de que no necesitas dividir los que están limpiamente dentro de tu polígono ya que ellos mismos son triángulos.

¿Esto es de alguna ayuda? Debería funcionar para cualquier polígono (convexo / cóncavo / con agujeros en ellos), creo, dado que lo que haces exactamente para intersectar cuadrados / triángulos maneja dichos polígonos.