algorithm - Anidando la máxima cantidad de formas en una superficie.
geometry computational-geometry (2)
Después de que Andrew en su respuesta me indicó la dirección correcta y me asignó el problema, decidí descartar los resultados de mi investigación en una respuesta por separado.
Este es de hecho un problema de empaque, y para ser más precisos, es un problema de anidación. El problema es matemáticamente NP-duro, y por lo tanto los algoritmos actualmente en uso son enfoques heurísticos. No parece haber ninguna solución que solucione el problema en un tiempo lineal, a excepción de los conjuntos de problemas triviales. Resolver problemas complejos toma de minutos a horas con el hardware actual, si desea lograr una solución con una buena utilización del material. Hay decenas de soluciones de software comercial que ofrecen agrupamiento de formas, pero no pude localizar ninguna solución de código abierto, por lo que no hay ejemplos reales en los que se puedan ver los algoritmos implementados.
En un artículo escrito por Benny Kjær Nielsen de la Universidad de Copenhague ( Nielsen ), se puede encontrar una excelente descripción del problema de anidación y de anidación de bandas con soluciones históricas.
El enfoque general parece ser mezclar y usar múltiples algoritmos conocidos para encontrar la mejor solución de anidamiento. Estos algoritmos incluyen la búsqueda local (guiada / iterada) , la búsqueda rápida en el vecindario que se basa en el polígono de no ajuste y la heurística de Jostling . Encontré un gran artículo sobre este tema con imágenes de cómo funcionan los algoritmos. También tenía puntos de referencia de las diferentes implementaciones de software hasta el momento. Este documento fue presentado en el Simposio Internacional sobre Programación 2006 por S. Umetani et al ( Umetani ).
Un enfoque relativamente nuevo y posiblemente el mejor hasta la fecha se basa en el Algoritmo Genético Híbrido (HGA), un híbrido que consiste en un recocido simulado y un algoritmo genético descrito por Wu Qingming y otros de la Universidad de Wuhan ( Quanming ). Lo han implementado utilizando Visual Studio, la base de datos SQL y la caja de herramientas de optimización de algoritmos genéticos (GAOT) en MatLab.
En la industria, a menudo hay un problema en el que necesita calcular el uso más eficiente del material, ya sea tela, madera, metal, etc. Por lo tanto, el punto de partida es X cantidad de formas de dimensiones dadas, hechas de polígonos y / o curvas. líneas, y el objetivo es otro polígono de dimensiones dadas.
Supongo que muchas de las suites CAM actuales implementan esto, pero al no tener experiencia en el uso de ellas o de sus componentes internos, ¿qué tipo de algoritmo computacional se usa para encontrar el uso más eficiente del espacio? ¿Alguien puede indicarme un libro u otra referencia que trate este tema?
Usted se está refiriendo a un conocido dominio informático del embalaje, para el cual hay una variedad de problemas definidos e investigaciones realizadas, tanto para el espacio bidimensional como para el espacio tridimensional.
Existe una cantidad considerable de material en la red disponible para los problemas definidos, pero para encontrarlo debe saber el nombre del problema que debe buscar.
Algunos paquetes bien podrían adoptar un enfoque heurístico (que sospecho que lo harán) y otros podrían hacer todo lo posible para calcular todas las posibilidades para obtener la respuesta correcta absoluta.