¿Cómo empacar polígonos dentro de otro polígono?

20

He ordenado algunas sábanas de cuero de las cuales me gustaría construir bolas de malabares cosiendo los bordes. Estoy usando los sólidos platónicos para la forma de las bolas.

Puedo escanear las láminas de cuero y generar un polígono que se aproxime a la forma de la lámina de cuero (como saben, es piel de animal y no viene en rectángulos).

Así que ahora, me gustaría maximizar el tamaño de mi bola de malabarismo.

En mi ejemplo, los polígonos son regulares, pero estoy buscando una solución con polígonos simples.

¿Cuál es el factor de escala más grande que puedo aplicar a mis polígonos para que todos quepan dentro de la hoja?

Estoy tratando de minimizar el desperdicio usando la mayor cantidad de material posible.

Obviamente, cortar la red de poliedros en polígonos individuales aumentará el espacio de combinación posible, pero también disminuirá la calidad de la geometría final, porque hay más costuras involucradas y errores acumulados. Pero esta pregunta no se trata de enumerar las diferentes formas de desplegar un poliedro. Se pueden considerar de forma independiente. Entonces los polígonos son polígonos simples.

Formalmente:

Entrada:

  • : un polígono simple (el objetivo)PAGS
  • S : el conjunto de polígonos que quiero colocar
  • sol : un gráfico de polígonos simples: cada nodo representa un polígono simple en , y hay un borde de borde entre cada par de polígonos que comparten un borde común norteS
  • α> =0 0,β> =0 0 (uso de material y conectividad)

Salida:

  • un factor de escalaF
  • H , un subgrafo desol
  • Lodo : una ubicación y un ángulo para cada polígono enV(sol)
  • Una medida de la calidad de la solución:metrometro=α.F+β.El |mi(H)El |El |mi(sol)El |

Maximice sujeto a estas condiciones:metro

  • El |V(H)El |=El |V(sol)El | (1)
  • El |mi(H)El |<=El |mi(sol)El | (2)
  • para cada polígono en , escalado por un factor en la ubicación está dentro de (3)SyoSSyoFLodo(Syo)PAGS
  • los polígonos en no se superponen (4)V(H)

(V (G) son los vértices en el gráfico, y S es el conjunto de polígonos, pero describen el mismo conjunto de objetos. Quizás haya una forma más compacta de hacerlo.)

Explicación de las condiciones:

  • (1) Quiero que todos los polígonos estén en el diseño final
  • (2) Algunas conexiones pueden romperse si es necesario
  • (3) (4) la pelota está hecha de cuero

Aquí está el polígono objetivo Hoja de cuero

Aquí está el conjunto de polígonos que quiero empacar: Red de poliedro

alecail
fuente
¿Estás hablando de polígonos convexos que quieres cortar?
A.Schulz
En mi caso, los polígonos son regulares, porque son las caras de los sólidos platónicos. Pero empacar polígonos simples también debería funcionar. ¿Por qué quieres saber si los polígonos que quiero empacar son convexos?
alecail
1
Si los polígonos no son convexos, siempre puede colocar un único polígono no convexo dentro del polígono original sin corte. Entonces esta pregunta no tendría sentido para los polígonos generales.
A.Schulz
No sé si esto es importante o no, pero ¿es el polígono delimitador (cuero) convexo o también puede ser cóncavo?
Paresh
44
Incluso el problema mucho más simple de empacar el número máximo de cuadrados en un cuadrado resulta difícil (lo siento, no tengo un enlace a mano, pero tropecé con una discusión sobre esto hace unos meses). Simplemente haga malabarismos con los polígonos a mano, probablemente no estaría demasiado lejos de lo óptimo.
vonbrand

Respuestas:

3

Esto pertenece a una clase de optimización de problemas llamada problemas de embalaje . En su caso, en lugar de un polígono regular como contenedor, tiene uno irregular, pero la idea sigue siendo la misma.
Estos problemas de optimización suelen ser NP-hard, por lo que no creo que haya una manera fácil de obtener la solución exacta y probar todas las combinaciones sería demasiado costoso.
Hay algunas personas interesadas en este tipo de problemas; He encontrado este enlace de algunos problemas de embalaje específicos resueltos: http://www2.stetson.edu/~efriedma/packing.html

La forma más fácil que veo es definir un centro aproximado de la lámina de cuero, mover el conjunto de polígonos hacia allí y, escalando hacia arriba y hacia abajo y verificando si el conjunto de polígonos está o no dentro del polígono objetivo, para obtener un factor de escala cada vez más cercano 'f' para su conjunto deseado de polígonos.

Pero, a menos que vaya a utilizar este factor para una producción de bolas de malabarismo a gran escala, probablemente sea suficiente hacerlo a mano.

Akronix
fuente