Cubra un polígono cóncavo con un número mínimo de rectángulos

11

Estoy tratando de cubrir un polígono cóncavo simple con un mínimo de rectángulos. Mis rectángulos pueden tener cualquier longitud, pero tienen anchuras máximas y el polígono nunca tendrá un ángulo agudo.

Pensé en tratar de descomponer mi polígono cóncavo en triángulos que produjeran un conjunto de rectángulos mínimamente superpuestos que limitaran mínimamente cada triángulo y luego fusionaran esos rectángulos en otros más grandes. Sin embargo, no creo que esto funcione para pequeñas muescas en los bordes del polígono. Los triángulos creados por los vértices reflejos en esas muescas crearán los rectángulos incorrectos. Estoy buscando rectángulos que abarquen / ignoren las muescas.

Realmente no sé nada sobre geometría computacional, por lo que no estoy muy seguro de cómo comenzar a hacer la pregunta.

Encontré otras publicaciones que eran similares, pero no las que necesitaba:

Algunos ejemplos: el negro es la entrada. El rojo es el resultado aceptable.

ingrese la descripción de la imagen aquí

Otro ejemplo: se prefiere la segunda salida. Sin embargo, generar ambos resultados y usar otro factor para determinar la preferencia es probablemente necesario y no es responsabilidad de este algoritmo.

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

Los polígonos que imitan curvas son extremadamente raros. En este escenario, gran parte del área de los rectángulos se desperdicia. Sin embargo, esto es aceptable porque cada rectángulo obedece a la restricción de ancho máximo.

ingrese la descripción de la imagen aquí

Además, este artículo me pareció cercano a lo que necesito:

Quizás una mejor pregunta es "¿Cómo puedo identificar porciones rectangulares de un polígono cóncavo?" ingrese la descripción de la imagen aquí

Aquí hay una imagen que muestra la implementación deseada: ingrese la descripción de la imagen aquí

El verde es el uso real del material. Los rectángulos rojos son los diseños. El azul es el MBR de todo el polígono. Estoy pensando que debería tratar de obtener pequeños MBR y completarlos. Los 2-3 rectángulos verdes en la esquina superior izquierda que terminan en el medio del polígono son caros. Eso es lo que quiero minimizar. Los rectángulos verdes tienen un ancho y alto mínimo y máximo, pero puedo usar tantas filas y columnas necesarias para cubrir una región. Nuevamente, debo minimizar la cantidad de rectángulos que no se extienden a través de la entrada. También puedo modificar la forma del rectángulo verde para que quepa en lugares pequeños que también es muy costoso. En otras palabras, es ideal obtener tantos rectángulos como sea posible para abarcar tanto como sea posible.

co.combinatorics cg.comp-geom Josh C.
fuente
3
Su título dice polígonos convexos, pero la pregunta habla de polígonos cóncavos. ¿Quizás necesites hacer algunas correcciones?
Ankur
1
@JukkaSuomela, en las dos primeras imágenes, el polígono es aproximadamente del mismo tamaño, y en la primera imagen, podría haber corrido tres rectángulos verticalmente como lo hice en la segunda. Sin embargo, esto es menos deseable. Creo que el truco tiene que ver con los perímetros de los rectángulos. Tal vez lo que estoy tratando de hacer es minimizar la cantidad de límite de rectángulo que está dentro del polígono y maximizar la cantidad de límite que es colineal con los bordes del polígono. Sin embargo, a veces los rectángulos deben derramarse fuera del polígono para cubrirlo completamente.
Josh C.
1
@ JohnMoeller, entiendo. Este es un problema en el que un humano puede identificar la solución fácilmente, pero es bastante difícil establecer el problema correctamente. El problema es similar a la colocación de alfombras o papel de pared y el problema real es estructural / arquitectónico. Estoy tratando de identificar regiones de diseños rectangulares que luego se llenarán con otra forma de teselación. Encontrar los rectángulos y manejar las regiones no rectangulares es el problema. Avísame si puedo explicarte más.
Josh C.
2
Creo que deberíamos abordar esto primero como una pregunta de modelado: el objetivo no es encontrar un algoritmo que resuelva un problema de optimización bien definido, sino el objetivo es definir el problema de optimización.
Jukka Suomela
3
@JoshC .: Quizás también sería útil que intentaras contarnos más sobre la aplicación del mundo real. De su descripción deduzco que, por ejemplo, cortar es bastante costoso; idealmente, las piezas rectangulares requerirían el menor corte posible. ¿Es esto correcto?
Jukka Suomela

Respuestas:

3

Esta es una variante de la cubierta del conjunto geométrico. Dependiendo de la configuración exacta, es posible que pueda hacer una buena aproximación. El problema es, por supuesto, NP-Hard. Los huersitics naturales son usar un algoritmo codicioso (siempre elija el rectángulo / tira que cubra la mayor parte del área aún no cubierta. La técnica alternativa es usar el pesaje de nuevo. Hay algunos resultados teóricos interesantes, pero, francamente, nada que sea demasiado útil en la práctica Una característica interesante que quizás desee probar es descomponer primero su polígono en un número mínimo de formas convexas (utilizando el algoritmo de programación dinámica Keil) y luego cubrir cada polígono convexo por separado ...

Sariel Har-Peled
fuente
No estoy familiarizado con el algoritmo de programación dinámica Keil. Sin embargo, encontré un método para trabajar usando una combinación de los algoritmos Rectángulo más grande inscrito y Rectángulo de límite mínimo con algunas variantes basadas en la heurística.
Josh C.
2

Creo que este documento puede ser de alguna ayuda. Obviamente no es el mismo problema, de hecho es el problema inverso, que cubre un rectángulo con polígonos, pero algunas de las ideas podrían ser un punto de partida. En particular, este problema inverso es NP-hard y sospecho que el suyo también puede serlo (aunque no hay una extensión obvia de la reducción hasta donde puedo decir).

E. Arkin, A. Efrat, G. Hart, I. Kostitsyna, A. Kroller, J. Mitchell y V. Polishchuk. Escandinavos finos en la parte superior del pastel: en la caja más pequeña de talla única. Diversión con algoritmos . p. 16-27. 2012

SamM
fuente
1
Gracias por su sugerencia. He estado trabajando con los departamentos de ingeniería y fabricación de mi empresa para aportar más aclaraciones a este problema. Todavía estoy esperando confirmar, pero ahora estoy pensando que un algoritmo que devolvería conjuntos de rectángulos inscritos más grandes funcionaría. Si bien no cubre completamente la forma, daría preferencia a las regiones ortogonales mientras deja las regiones no ortogonales a algunas heurísticas. El único truco es maximizar esas regiones ortogonales. Vea mi última imagen con las 9 figuras parecidas a lamda.
Josh C.