Algoritmo de empaque eficiente para polígonos irregulares

Question

Estoy buscando un algoritmo de empaque que reduzca un polígono irregular a rectángulos y triángulos rectos. El algoritmo debe intentar usar la menor cantidad de formas posibles y debe ser relativamente fácil de implementar (dada la dificultad del desafío). También debería preferir rectángulos sobre triángulos donde sea posible.

Si es posible, la respuesta a esta pregunta debe explicar la heurística general utilizada en el algoritmo sugerido.

Esto debería ejecutarse en tiempo determinista para polígonos irregulares con menos de 100 vértices.

El objetivo es producir un colapso "sensible" del polígono irregular para un lego.

La primera heurística aplicada a la solución determinará si el polígono es regular o irregular. En el caso de un polígono regular, vamos a utilizar el enfoque descrito en mi puesto similar sobre polígonos regulares: Efficient Packing Algorithm for Regular Polygons

alt text http://img401.imageshack.us/img401/6551/samplebj.jpg

Answer 1

No sé si esto le daría la respuesta óptima, pero sería al menos dar una respuesta:

1. Calcule una triangulación de Delaunay para el polígono dado. Existen algoritmos estándar para hacer esto que se ejecutarán muy rápidamente para 100 vértices o menos (consulte, por ejemplo, this library here.). El uso de una triangulación Delaunay debe garantizar que no tenga demasiados triángulos largos y delgados.
2. Divida cualquier triángulo no recto en dos triángulos rectos bajando una altitud desde el ángulo más grande al lado opuesto.
3. Busque triángulos que pueda combinar en rectángulos: dos triángulos rectángulos congruentes (no imágenes espectrales) que comparten una hipotenusa. Sospecho que no habrá muchos de estos en el caso general a menos que su polígono irregular tenga muchos ángulos rectos para empezar.

Me doy cuenta de que hay muchos detalles para completar, pero creo que comenzar con una triangulación Delaunay es probablemente el camino a seguir. Las triangulaciones de Delaunay en el plano se pueden calcular de manera eficiente y generalmente se ven bastante "naturales".

EDITADO PARA AGREGAR: ya que estamos en ad-hoc heuristicville, además de los algoritmos codiciosos que se discuten en otras respuestas también debe considerar algún tipo de estrategia de dividir y conquistar. Si la forma no es convexa como su ejemplo, divídala en formas convexas cortando repetidamente desde un vértice reflejo a otro vértice de una manera que se aproxime a la bisección del ángulo reflejo como sea posible. Una vez que haya dividido la forma en piezas convexas, consideraría a continuación dividir las piezas convexas en piezas con buenas "bases", piezas con al menos un lado con dos ángulos agudos o derechos en sus extremos. Si una pieza no tiene esa "base", deberías poder dividirla en dos a lo largo del diámetro de la pieza, y obtener dos piezas nuevas, cada una con una "base" (creo). Esto debería reducir el problema al tratar con polígonos convexos que son algo así como trapezoidal, y a partir de ahí un algoritmo codicioso debería hacerlo bien. Creo que este algoritmo subdividirá la forma original de una manera bastante natural hasta que llegue a las piezas trapezoidales algo sociables.

Answer 2

¡Ojalá tuviera tiempo para jugar con esto, porque suena como un problema realmente divertido!

Mi primer pensamiento (al mirar el diagrama anterior) sería buscar 2 ángulos rectos adyacentes girando en la misma dirección.Estoy seguro de que no detectará todos los casos en los que un rectángulo ayudará, pero desde el punto de vista de un usuario, es un caso obvio (esquinas cuadradas en el exterior = esto debería ser un rectángulo).

Una vez que haya encontrado un par adyacente de ángulos rectos, tome la longitud de la pata más corta, y hay un rectángulo. Resta esto del polígono que queda en mosaico y repite. Cuando no haya más rectángulos externos obvios para eliminar, entonces haga su tarea de mosaico normal (la respuesta de Peter suena genial) sobre eso.

Negación: No soy un experto en esto, y ni siquiera lo he probado ...