Teselar un polígono arbitrario mediante mosaico de triángulos

Question

Necesito rellenar 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.

La siguiente se presume:

• El polígono puede ser (puntos, pero de bonificación si usted viene con un algoritmo que trabaja para formas cóncavas) convexas
• El polígono tiene un número arbitrario de bordes (3 o más)
• la cantidad de teselado (preferiblemente el número de vértices añadidos por el algoritmo) debe parametrizar
• bordes del polígono pueden ser divididos por el algoritmo
• Tr Los iangles 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 deben ser pocos en lugar de muchos. Esto probablemente seguirá del punto anterior (es decir, el algoritmo debería producir una "malla limpia").

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

Answer 1

Como Jason Orendorff señaló, usted debe tratar de usar triángulo 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 this publications page. 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.

Answer 2

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

Algunos pseudocódigo:

• lugar de un eje alineado a encerrar herméticamente alrededor de la plaza polígono.
• Subdividir cada cuadro en cuatro elementos (similar a un árbol cuádruple), donde el número de iteraciones determina la "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.
• Las cajas exactas para los cuadrados de intersección se dejan como 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.

¿Es esto de alguna ayuda alguna? 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.

Answer 3

¿Hace Triangle hacer lo que quiere?

(Las explicaciones de los algoritmos en ese sitio son mejores que cualquier cosa que pudiera ocurrir.)

Answer 4

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

• Tessellate el polígono
  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
• Girar bordes entre triángulos donde el área dividida por el perímetro es más pequeña una vez que el borde se hace girar en el nuevo estado.

Ésta es 2 pasos, por lo que puede ser más eficiente para recortar de forma iterativa la 'mejor' la oreja para obtener resultados más uniformes, por lo que no tiene que volver a organizar la topología como un segundo paso (tu caso es distinto).
(Tenga en cuenta que las razones por las que se utilizan 2 pasos aquí es que no siempre es necesario calcular una distribución más pareja).

---

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

aplicación de trabajo escrito en C,
que toman y el regreso de POD (float[2] matriz, rellenando una matriz uint[3]):

• polyfill2d.c (teselado)

• polyfill2d_beautify.c (ajusta topología para obtener resultados más uniformes)

• también hizo un port of polyfill2d.c to Rust

(Nota, el recorte del oído se basa en libgdx con optimizaciones espaciales a los controles de intersección, para escalar hasta miles de lados sin impacto en el rendimiento tan significativo, ya que el recorte todos los oídos era el registro de todos los-otros-puntos cada vez).