Empaque sus cortes de madera con algoritmos genéticos

Al leer (¡o escribir!) La-Tecnologia, encontramos que las personas a menudo nos resuelven problemas que ni siquiera sabíamos que teníamos. Tómalo [Jack Qiao]SVGnest por ejemplo. Si alguna vez ha utilizado una cortadora láser, por ejemplo, probablemente haya pensado durante uno o dos segundos en la mejor forma de empaquetar los objetos en una hoja, hacer su mejor tiro y luego seguir adelante. Pero si tuviera muchas piezas, y sus formas fueran irregulares, y quisiera minimizar el costo del material, se le ocurriría algo mejor.

SVGnest, que funciona con un navegador, toma muchos formularios SVG y un cuadro de restricción como entrada, y luego intenta empaquetarlos todos lo mejor posible. De hecho, optimizar la colocación es una propuesta computacionalmente costosa, y esto tiene en cuenta el orden de colocación para arreglar y permitir solo rotaciones de 90 grados de cada pieza.

Después de considerar todos los posibles órdenes en los que pones las piezas, se vuelve ridículamente costoso por computadora, por lo que SVGnest hace trampa y usa un algoritmo genético que básicamente intercambia algunas piezas e intenta mejorar muchas, muchas veces. Hacerlo por casualidad sería una tontería, por lo que la rutina primero empaca las piezas más grandes y luego llena las pequeñas donde encajen, quizás moviendo las grandes para acomodarlas.

Eso es mucho trabajo de computadora, pero el resultado final es asombroso. SVGnest incluye mejores formas de las que podríamos esperar, así como algunos programas comerciales de anidación. Kudoj. Y ahora que el software está escrito, tan pronto como se encuentre con este problema, tendrá un medio para llegar a la solución. Gracias [Jack]!

  • pelrun dice:

    Awwww, ¿javascript?

    • pelrun dice:

      (Aparte de eso, creo que esto es bastante impresionante).

    • ESTOLA dice:

      JavaScript es muy capaz en las computadoras modernas. Lo uso constantemente: solo abro .htm en mi escritorio y lo envío a un editor de texto.

      Aunque mi JavaScript garantiza fallar en cualquier máquina o navegador que no sean los que usé para desarrollar el código, todavía funciona.

      Mi computadora sintética HDL es de cuatro núcleos a 2.6 GHz, por lo que es realmente sorprendente lo que puede hacer con un simple JavaScript antiguo.

      Por supuesto, uso JavaScript solo para las cosas más simples y rápidas, cualquier cosa más difícil y usaré algo como Lua.

      Encuentro que JavaScript es útil para gráficos u otros resultados visualizados, es por eso que un navegador está hecho para eso.

    • DV82XL dice:

      Hacer el trabajo.

  • trenzado morado dice:

    ¿Podría usarse esto para empacar UV para modelos 3D?

    • Jacobo dice:

      OP aquí. No pensé en esa aplicación, pero lo que se muestra a continuación es lo mismo. El principal obstáculo sería la importación / exportación de datos UV.

      • Lupus Mecánico dice:

        Jack, ¡tienes que venderle esto a pepakura!

      • trenzado morado dice:

        Recordé que hay una plancha que hace algo similar http://www.texturebaking.com/features-benefits/

        Me pregunto si su método funcionaría para uv, cómo podría compararse con la plancha y otras soluciones.

    • Sr. Nada dice:

      Pensé lo mismo. El mapeo UV siempre ha sido un gran obstáculo para mi creatividad. haces un modelo y sabes lo que quieres hacer con la textura, pero tienes esta tarea tediosamente larga y tediosa entre el modelado real y la apertura de una tienda de fotografía con un patrón y el vertido de cuatro píxeles.

      esto sería especialmente útil si necesita un segundo canal uv donde cada polígono tiene un espacio único, por ejemplo, para mapas normales (especialmente usando técnicas de horneado). luego, el canal principal permite duplicar y dividir áreas para mantener la densidad de píxeles. Por lo general, desea que haya grandes trozos de polígonos adyacentes que se hayan expulsado para eliminar las costuras. pero normalmente los mapeo en secciones antes de intentar hacer coincidir todas esas secciones. por lo que el algoritmo ayudaría en ambas situaciones.

  • murray dice:

    ¿Intercambios 2 y pruebas? Eso no suena como un algoritmo genético, suena como un tipo de burbuja.

    • pelrun dice:

      Quizás quieras leer un poco más. No "intercambia 2 y prueba". Los entornos se mutan aleatoriamente y las mutaciones con la mejor puntuación se emparejan para producir descendencia para la próxima generación. Nada de eso está en su tipo de vejiga.

  • George Graves dice:

    Los cortadores láser distorsionan un paño durante el corte. Los pequeños cortes tienden a tirar del plástico de una forma u otra. Así que 1/4 ″ parece ser bueno, y realmente no eres demasiado material. Madera, no tanto. Pero me encanta esta idea.

  • petardo dice:

    Girar cosas sobre madera contrachapada no es tan agradable. Algunas uniones comienzan a verse realmente mal cuando una textura de madera se tornea en una parte pero no en la otra. Pero un gran concepto.

    • fonz dice:

      lo mismo ocurre con la tela

    • diferencia dice:

      Puedes controlar la rotación. El valor predeterminado es 4 rotaciones (rotaciones cardinales), pero si lo configura en 2, solo obtendrá orientaciones "arriba" o "abajo".

  • wyojustin dice:

    ¡Por qué no pensé en eso! Mirinde.

    El viernes 22 de enero de 2016 a las 4:02 am, La-Tecnologia escribió:

    > Elliot Williams publicó: "Leyendo (¡o escribiendo!) La-Tecnologia, encontramos que la gente a menudo nos resuelve problemas que ni siquiera sabíamos que teníamos. [Jack Qiao]SVGnest por ejemplo. Si alguna vez usó un cuchillo> láser, por ejemplo, probablemente haya pensado por un segundo o ">

  • duro suave dice:

    ¿Por qué no tomar un buen simulador de física 2d, agregar algo de gravedad, a través de todas las piezas en una caja, y luego agitar la caja un poco? Entonces, llenar bien las partes huecas sería difícil.

    • duro suave dice:

      oh, creo que llena las partes huecas que necesitarías algún efecto de túnel

      • duro suave dice:

        ¿Te refieres a algo como un túnel cuántico?

        • duro suave dice:

          Sí, tal vez, pero ¿por qué respondes a tus propios comentarios?

          • duro suave dice:

            Yo, yo mismo y todos respondemos.

    • Daniel dice:

      Utilizo esta técnica cuando vuelvo a poner los juguetes de mis hijos en la caja. Primero las piezas grandes como vehículos y esas cosas. Luego vierta figuras y más pequeñas hasta llenas hasta el borde y agite. Repita según sea necesario. Paquetes increíblemente densos.

    • Vejestorio dice:

      Esto es un poco como una forma simple de calcinación simulada ...

    • Greenaum dice:

      Debido al "embalaje de partículas". Si pones muchas cosas de formas aleatorias en una caja y las sacudes, las más pequeñas terminan subiendo hasta la parte superior. No obtienes un empaque tan óptimo. Se ha estudiado y se presenta en cosas como cajas de copos de maíz. De hecho, es un pequeño problema.

      • darren dice:

        Las cosas más grandes en realidad terminan subiendo porque las cosas pequeñas caen en los pequeños huecos que se forman debajo de las cosas grandes cuando se sacuden. Los problemas descritos son reales.

        • Greenaum dice:

          ¡Eso es exactamente lo que quise decir!

          De hecho, la idea de OP podría funcionar en ausencia de gravedad o en ausencia de gravedad simulada. Pero sí, el empaquetado de partículas ha causado problemas en todo tipo de aplicaciones del mundo real.

          En cuanto a las simulaciones, sin embargo, creo que algo genético las haría menos calculadoras.

  • Miroslav dice:

    Pensé en esto, pero no lo logré. Mi sombrero es para el desarrollador. Mirinde.

    • kratz dice:

      Hice un algoritmo de anidación una vez en el trabajo, aunque mis límites eran partes rectangulares con una dirección de grano y la posibilidad de un grano compatible (partes que deben estar una al lado de la otra). El comienzo del algoritmo fue el mismo, ordenado por tamaño y primera ubicación apropiada, pero sin el paso genético adicional (probablemente no sea de mucha ayuda con los rectángulos, además la mayoría de las partes no pueden rotar).

      Los rectángulos son fáciles, sin embargo, la detección de colisiones es bastante simple y simplemente puede rastrear los ángulos para los puntos de inserción. Hay mucho más para lograrlo con formas irregulares. Esta persona ha completado una tarea.

    • Andrés Pullin (@AndrewPullin) dice:

      Sí, suena familiar. Hace algún tiempo en HaD, incluso hice el comentario sobre cómo el software de herramientas y cuchillos de código abierto fue un gran paso para causar la explosión 3D de bricolaje. Solo un programador general que permite que exista la canalización y hace bien el trabajo. Debido a que el corte por láser es la otra herramienta importante en este espacio de construcción accesible y rápida, claramente se ha requerido una herramienta de conducto similar para empaque 2D.

      Y luego nunca lo hice, porque soy vago: P

  • Rodney McKay dice:

    ¿Sería útil esto para resolver el problema del vendedor ambulante?

    • kratz dice:

      Bueno, el vendedor ambulante y el embalaje de contenedores 2d son problemas de NP-Hard, por lo que supongo que podría asignar soluciones de uno a otro.

    • sky99 dice:

      No solucionará el problema.
      Los algoritmos genéticos son buenos para encontrar una solución, no LA solución.
      El problema del viajante es difícil porque uno quiere
      LA MEJOR SOLUCIÓN QUE UNA MEJOR SOLUCIÓN.

    • Andrés Pullin (@AndrewPullin) dice:

      https://cs.gmu.edu/~sean/book/metaheuristics/

  • Chorro de agua dice:

    ¿Qué hay de agregar pestañas a las piezas para evitar que se muevan?

  • Me dice:

    ¿Cómo se puede utilizar esto para la impresión 3D con Slic3r y Repetier?

  • Somun dice:

    "Utiliza un algoritmo genético que básicamente intercambia algunas piezas e intenta mejorar muchas, muchas veces"
    No, este no es un algoritmo genético. Puede que sea una búsqueda local. ¡Una parte importante de GA tiene recombinación!

    • Elliot Williams dice:

      GA elige compañeros más adecuados con una mayor probabilidad. Es un montaje de puerta trasera de acuerdo con la función objetivo, IMO. Mejor podría redactarlo en el artículo.

      Pero también llamo a las redes neuronales (de capa única oculta) "regresión con funciones logísticas", así que no me escuches. Incluí un enlace para aquellos que querían leer más.

      • Somun dice:

        Llamarlo escalada por la puerta trasera es lo mismo que llamarlo búsqueda local 🙂 De todos modos, gracias por la respuesta.

  • RoGeorge dice:

    Buena suerte ordenando tus cortes.

  • Tricon dice:

    Jack hizo una actualización
    https://deepnest.io/

  • Daniel Green dice:

    ¿Alguien ha visto algo como esto para la impresión 3D? Sería bueno utilizar esta técnica para empacar la placa de construcción.

Alana Herrero
Alana Herrero

Deja una respuesta

Tu dirección de correo electrónico no será publicada.