1、重叠移除算法

1-1、ILSQN（梯度下降法）

参考论文：《An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem》Takashi Imamichi ,∗, Mutsunori Yagiura , Hiroshi Nagamochi

第一步：初始计算各个NFP、IFP

第二步：FindBestPoint方法1、2 找点

参数 X n个多边形的位移向量,长度为n，数据元素是(x,y)的线性表

参数 O n个多边形的旋转角度，长度为n，数据元素是度数[0,90,...]的角度表的线性表，每个多边形可以有多个角度

参数 i 第i个多边形

1.1、ComputeNfpVI(X,O,int i)

根据i当前位置,选择FindBestPosition的候选位置即V(o)+I(o),V(o)是集合：(i与其他多边形的NFP的顶点集合)+(i与板内部IFP的顶点),

I(o)是集合:V(o)组成的多边形的交点.这里的NFP和IFP初始化时已得到，现在是根据当前的X和O平移过去找交点,即V(O)根据平移可以直接得到，I(o)需要求解.

1.2FindBestPoint与FindBestPoint2

FindBestPoint2与1的区别是：候选位置在顶点中随机取K个，不用交点

第三步：:SwapTwoPolygons 交换零件

三种情况：

情况1大概率不满足，不考虑这种情况，只作为论文比较用

第四步：Separate 分离微调

拟牛顿法

第五步：MinimizeOverlap 最小重叠

第六步：ILSQN 主方法

1-2、GCS（布谷鸟搜索法）

对应代码：GuidedCuckooSearch()、CuckooSearchWithBLF()

参考论文：《A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering》Ahmed Elkeran 2013

第一步：布谷鸟搜索

第二步：最小化重叠

第三步：GCS主方法

布谷鸟搜索算法使用了局部随机游走和全局探索性随机游走的平衡组合

局部随机游走

全局随机游走，Lévy flights莱维飞行

2、零件组合算法

2-1、Pairwise聚类

用python实现的源码：https://github.com/la667-j/PolygonPairwise

参考论文：《A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering》Ahmed Elkeran 2013

第一步：找到最可能的位置

取多边形上的点与（凸包-多边形）边界最远的点，多边形上的点也必须满足是（凸包-多边形）的对边的点

第二步：计算Cr1+Cr2

结果筛选，取Cr1+Cr2最大的

cr1：（多边形与凸包的交集的面积和）/（凸包-多边形）的面积和 ，取ij极大值者

cr2：（pi面积+pj面积）/（pi与pj的并集的凸包的面积）

3、计算NFP算法

3-1、移动碰撞法

参考论文：《Complete and robust no-fit polygon generation for the irregular stock cutting problem》E.K. Burke, R.S.R. Hellier, G. Kendall, G. Whitwell *

第一步：接触边缘检测

针对多边形B的每条边测试多边形a的每条边来实现。每对接触的边（一对来自多边形A，一对来自多边形B）与接触顶点的位置一起存储。

第二步：潜在向量生成

必须从多边形A的边或从多边形B（反转该边来找到平移向量）导出。

(i) ：两条边在顶点处接触。需要正确识别潜在平移矢量是从静止边缘还是轨道边缘导出。

(ii) ：环绕边的顶点接触静止边的中间。平移向量仅使用两条边接触的点和固定边的末端顶点。

(iii)：静止边的顶点接触环绕边的中间。平移向量由接触的点和轨道边的末端顶点组成，反转矢量方向。

(i)可能的情况

首先34排除轨道边（接触点是末端点，结果为空向量），同理56排除固定边，再根据左右关系排除3，5

例子：

第三步：寻找可行的向量

可以基于指示特定的潜在平移是否适合于这些边缘的左/右区域的并集来定义静止多边形和轨道多边形的接触边缘之间的位置关系。对于要被识别为可行的潜在平移向量，它必须适合于每对接触边缘。

识别可行的平移角度范围（由圆弧指示)

排除图9 a1的过程，存在不适合接触边缘（a2,b3）（a3,b3）

第四步：修剪可行向量

在多边形B的每个顶点处投影平移向量，并测试其与多边形a的所有边的相交。

将平移向量从多边形a的所有顶点投影回来（通过将平移向量的结束顶点平移到每个顶点上），并与多边形B的所有边执行相交测试。

第五步：应用可行向量

将修剪的平移向量附加到到目前为止创建的部分非拟合多边形的末端，并且多边形B由修剪的平移向量平移。执行测试以检测多边形B的参考点是否已返回到其初始起始位置。

特殊情况：涉及联锁的凹面、拼图片或孔

将多边形A和多边形B的未遍历/未标记 边应用如下过程：（即外环循环过程中）

基于识别可行的接触但非相交的起始位置的方法，利用该方法可以使用前面描述的滑动技术来生成非拟合多边形构造的剩余内环。

给定多边形a的一条边e，可以检测到沿e的轨道多边形B的潜在起始位置。这个过程涉及到滑动多边形B，使它的每个顶点依次与e的起始顶点对齐。执行以下步骤：

如果这些多边形没有在这个位置上相交，则是可行位置。通过检查多边形B的两条连接边（在接触顶点处连接）是向右还是平行于边e。如果多边形B的任何一条连接边都在e的左侧，那么它们将在多边形A的内侧平移，并且可以立即消除，因为它们在沿着向量e滑动时永远不会产生可行的起始位置。

不沿a5滑动（b4在a5左侧）

沿a5滑动，两个连接的边b1、b2都是在边e的右边

如果相交，对这个向量进行修剪（过程是相同的）。

直到所有边顶点的可能性已经检查。

3-2、轨迹线法

用python实现的源码：https://github.com/la667-j/SimpleNFP

参考论文：《The irregular nesting problem: a new approach for nofit polygon calculation》L Huyao，H Yuanjun，J A Bennell

计算B上所有可能的边顶点和边缘滑动的路径，这些称为跟踪线段，其次，识别形成NFP外壳的跟踪线段，最后，识别任何跟踪线段形成内部孔的NFP。

第一步：计算顶点是否可以接触到边

对多边形A顶点p2，计算边(p1-p2)的法向量start，边(p2-p3)的法向量end

对多边形B边(pt1-pt2)的法向量是否在(start,end)范围内，如果是，则(pt1-pt2)加到跟踪线段线段集合。

对A的每个顶点，B的每条边执行以上操作；同理对B的每个顶点，A的每条边执行以上操作。

跟踪线段举例（Ptra1-Ptra2）（Ptra2-Ptra3），根据抓手点平移(PA1-PA2)(PA2-PA3)得到

第二步：识别形成NFP外壳的跟踪线段

1、从跟踪线段中选择最低点，并在起始点等于此最低点的线段中，选取与X轴形成最小角度的最低点作为起始线段

1. 获取与起始线段相交的所有线段，从起点最近的交点截断起始线段，并将此截断的线段添加到框多边形边集合中
2. 获取在截断点处与起始线段相交的所有线段，在这些线段中，取形成与起始线段相交的最小角度的线段作为下一个起始线段
3. 重复步骤2和步骤3，直到起始线段返回到第一个起始线段

网格加速运算

对于网格中的每个单元格，可以通过此索引定位与此单元格相交的所有线段。

特殊情况：内部嵌套NFP、孔

假设B完全在A内：

1. 寻找跟踪线的初始过程与第一步相同，只是A是顺时针方向的。
2. 在每个交点上将每个线段分解成许多较短的线段。
3. 从每个折线段开始，通过重复找到右侧的线段来找到一个内部的顺时针循环
4. 检查每个提取的循环，以验证它是一个NFP。在这里，没有必要检查所提取的循环中的每个顶点。只检查它的第一个边的中点

线段或点：如果有一个拟合点，至少有三个跟踪线段将在同一点相交

线段

点：五个跟踪线段相交

举例：

4、排版算法

4-1、阵列法

用python实现的源码：https://github.com/la667-j/NestingLattice

参考论文：《Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet》M. Teresa Costa, A. Miguel Gomes , Jose´ F. Oliveira

利用outerNfp求出三个同样的零件同样角度不重叠且互相接触的位置，为排版方便固定竖直方向的零件作为v0，右边的零件作为v1

4-2、左底法

对应代码：GetBottomLeft()

参考论文：《A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation》Sahar Chehrazad, Dirk Roose and Tony Wauters

解析线（Resolution Line）：在x轴上，以恒定的距离R划分空间，形成一系列垂直于x轴的直线，每条直线的x坐标为x=i*R，其中i是整数

解析算法用python实现的源码：https://github.com/la667-j/polygonSweepLine

将多边形半离散的用解析线的形式表示出来，

这样每个多边形的重叠可以根据比较相同索引的y区间来判断。

4-3、天际线法（针对矩形零件排版）

对应代码：NestOnlyRectangular

参考论文：《 Novel Heuristic and Metaheuristic Approaches to Cutting and Packing》 G Whitwell 2004

第一阶段：最佳适合放置启发式，排版前n个

将已摆放的零件表示为线段的形式，下一个零件从最低y的位置开始尝试，如果失败，抬高最低y至最低邻居区间，循环尝试

最佳适合放置启发式--放置下一个零件时，分三种方法：1、靠右 2、靠低的一方（shortest） 3、靠高的一方(tallest)

全部放置完成或者放不下，调整最高的位置，尝试旋转90度

第二阶段：左下角填充及模拟退火排剩余m个（越靠后可选的尺寸越少，使用模拟退火优化）

4-4、遗传算法（针对矩形零件排版）

对应代码：StartGeneticAlgorithm()

参考论文：《On genetic algorithms for the packing of polygons》L Fogel 1993

1）初始

种群：m个个体（零件顺序）

结果评估f()：排版后矩形阶梯剩余面积

2）交叉变异

归一化结果评估值

每个个体分配一个概率区间

随机取两个[0,1)之间的值i、j，判断属于以上哪个区间则交叉这两个个体

交叉：随机p处起始，将“i”中的q个元素复制到新排列的开头，剩余元素依次取“j”中的不重复元素

变异：概率pm，反转序列，交换元素，旋转元素