帮酷LOGO
  • 显示原文与译文双语对照的内容
An open source vector nesting tool

  • 源代码名称:SVGnest
  • 源代码网址:http://www.github.com/Jack000/SVGnest
  • SVGnest源代码文档
  • SVGnest源代码下载
  • Git URL:
    git://www.github.com/Jack000/SVGnest.git
  • Git Clone代码到本地:
    git clone http://www.github.com/Jack000/SVGnest
  • Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/Jack000/SVGnest
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
  • SVGNest

    SVGNest: 基于浏览器的矢量嵌套工具。

    演示:http://svgnest.com

    ( 需要SVG和webworker支持) 。 移动警告:运行演示是CPU密集型。

    引用( PDF ):

    什么是"嵌套"?

    给出一个正方形的材料和一些需要激光切割的字母:

    letter nesting

    我们想用尽可能少的材料把所有的字母都装进正方形。 如果一个正方形不够,我们也希望最小化使用的方块数。

    CNC世界称为"嵌套",而软件这种通常针对工业客户和非常昂贵的。

    SVGnest是一种免费和开源的替代方案,用[ e 中列出的轨道方法解决了这个问题。 Burke等,使用遗传算法进行全局优化。 适用于任意容器和凹边情况,并可以与现有的商业软件进行匹配。

    non-rectangular shapes

    它还具有part-in-part支持,用于将零件放置在其他零件的孔中。

    non-rectangular shapes

    用法

    确保所有零件都已经转换为轮廓,并且没有轮廓重叠。 上传SVG文件并选择其中一个轮廓作为 bin 。

    所有其他轮廓都自动作为嵌套的零件进行处理。

    算法概述

    在对矩形装箱问题存在良好启发的同时,在现实世界中,我们关心的是不规则的形状。

    策略由两个部分组成:

    • 放置策略( IE 。如何将每个零件插入一个纸盒)?
    • 和优化策略( IE 。 插入的最佳顺序是什么?

    正在放置零件

    这里的关键概念是"无拟合多边形"。

    给定多边形A 和B,我们要在A 周围,使它们总是触摸但是不相交。

    No Fit Polygon example

    产生的轨道是 NFP 。 包含B的所有可以能的展示位置,这些展示位置接触以前放置的部件。 然后我们就可以在NFP上选择一个点作为位置位置。

    类似地,我们可以为零件和容器构造一个"内部拟合多边形"。 这与NFP一样,只是环绕的多边形在固定的平面内。

    当两个或者多个部件已经经放置时,我们可以以采取以前放置部件的NFPs的联合。

    No Fit Polygon example

    这意味着我们需要计算 O(nlogn) NFPs来完成第一个封装。 尽管有方法可以以减轻这一点,但是我们采用了具有优化算法性能的强力方法。

    多目标优化

    现在我们可以放置零件了,我们需要优化插入顺序。 下面是一个错误插入顺序的示例:

    Bad insertion order

    如果放置了大的"c",它内部的凹空间将不会被利用,因为所有可以能填充的部分已经经被放置。

    为了解决这个问题,我们使用"first-fit-decreasing"启发式。 较大的零件先放置,最后部分较小。 这是相当直观的,因为较小的部分往往充当"砂"来填充较大部分的间隙。

    Good insertion order

    这个策略给我们一个好的开始,我们想探索更多的解决方案空间。 我们可以以随机的随机的插入顺序,但我们可以能做的更好的遗传算法。 ( 如果你不知道什么是 GA,那么本文将是非常容易理解的阅读)

    评估适应性

    在遗传算法中,插入顺序和零件的旋转形成基因。 适应度函数遵循以下规则:

    • 最小化unplaceable部件的数量( 由于它的旋转而不能容纳任何容器的零件)
    • 最小化使用的纸盒数量
    • 最小化所有放置零件的宽度

    第三个是任意的,因为我们还可以优化矩形边界或者最小凹壳。 在实际世界中使用的材料可以以是矩形的,这些选项往往会导致使用的材料长。

    因为基因中的小突变会导致整体健康的大变化,因这里人体的个体可以能非常相似。 通过缓存 NFPs,可以快速评估新个体。

    性能

    SVGnest comparison

    在运行了大约 5分钟后,执行类似于商业软件的操作。

    配置参数

    • 部件之间的空间:零件之间的最小间距( 例如。 用于激光切割,CNC偏移 等等 )
    • 曲线公差:在SVG单位或者中,可以为贝塞尔曲线和圆弧的线性近似值提供最大误差。 如果曲线部分看起来有点重叠,则减小该值。
    • 部分旋转:可能为每个零件计算的旋转次数。 4只表示基本方向。 较大的值可以改善结果,但收敛速度较慢。
    • 遗传算法:遗传算法的种群大小
    • 突变率:每个基因或者零件放置的突变探针。 1 -50的值
    • 零件的部分:启用时,将零件放置在其他零件的孔中。 默认情况下是关闭的,因为它可以是资源密集
    • 按以下步骤计算凹区:启用时,可以使用一些性能和放置鲁棒性来解决凹边缘情况,从而降低凹陷的成本:

    Concave flag example

    • 递归放置( 将零件放置在其他零件的孔中)
    • 自定义适应功能( 重力方向等)
    • 单击停止按钮时杀死工作线程
    • 修正NFP生成中的某些边缘情况



    Copyright © 2011 HelpLib All rights reserved.    知识分享协议 京ICP备05059198号-3  |  如果智培  |  酷兔英语