Algoritmo para ajustar polígonos 2D en un área?
https://stackoverflow.com/questions/1824711
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Hay un estándar para esto? Nombre del algoritmo?
Di: Tengo 10 polígonos de diferentes tamaños. Tengo un área de tamaño específico.
Quiero saber cómo llenar la mayoría de los polígonos en esa área y cómo se ajustan.
Nota: Los polígonos pueden rotarse según el conjunto de restricciones.
Solución
Un posible nombre es un Problema de embalaje . Está relacionado con el Problema de la mochila . Estos problemas tienden a ser NP-hard, y muchos requieren heurística. Si puede restringir las formas permitidas de polígonos y del área, puede existir un algoritmo más eficiente para su caso especial.
Otros consejos
Puedes echar un vistazo a " Dancing Links " en Wikipedia para la solución de Donald Knuth al problema de cobertura exacto, que incluye mosaico, su pregunta puede considerarse como un problema de mosaico
SI (eso es un gran si) todos tus polígonos eran rectángulos, y el área en la que deben encajar también es un rectángulo, entonces esto se llamaría bin-embalaje, Google te abrumará con información sobre esto. Si no lo están, entonces supongo que está buscando una variante de empaquetado de basura, y supongo que un poco más que está en un problema de NP para el cual 'probar y probar' es el mejor algoritmo disponible.
