【学习ing】二维不规则多边形排样问题
关于nesting、NFP（no-fit polygon）的学习
阅读论文
主要是：
Complete and robust no-fit polygon generation for the irregular stock cutting problem
Novel Heuristic and Metaheuristic Approaches to Cutting and Packing
An effective heuristic for the two-dimensional irregular bin packing problem
时间
2019-10月
概述
针对packing and nesting 问题，在看了一些论文之后的总结。问题描述：简单而言就是 如何合理的将很多个不同形状的shapes【规则矩形/不规则弧形/凹/凸多边形/带孔。。。】排放在一个Object内，使shapes在互不重叠的情况下，需要的object最小（利用的长度、宽度、面积或者数量）。在现实中可以节约原材料，减少浪费。
引入
矩形排样的研究方法相对成熟，对于二维不规则图形，可以通过求取最小包络矩形的方式将问题转化为矩形排样，但是对于大尺寸不规则图形，边角空间有很大的浪费，利用率不高。
网格划分：将object和shapes划分成网格，并使用0-1矩阵来描述空间被占用的情况，再进行优化。划分粒度对结果影响较大，太大会增大误差，太小会加大计算代价。
问题分类
按照需要考虑的参数数量分：一维（eg：只考虑质量的运输问题）、二维（eg：纺织行业的布料分割、钣金行业的零件布局、船舶行业的堆场问题…）、多维（eg：需要考虑长、宽、高、重量的装载问题…）
按照shapes分：矩形排样、不规则图形排样（直线、弧、孔…）
按照object分：给定长宽，要求使用个数最少化[钣金行业]；固定一边，要求利用最少长度[纺织行业]等等…
按照切割方式：一刀切/允许断刀（这对图形的排样约束有影响，一刀切要求shapes的边界必须在构成直线，以免被拦腰截断。）
。。。。等等
nesting 步骤
- 底部几何算法
- 排样策略——selection+placement
- 优化/搜索算法
【底部几何算法】是处理nesting问题最基础的步骤，主要是用来计算、判断图形之间的位置关系、重叠与否、需要移动多少距离才才达到touch;【排样策略】主要是采用一些启发式规则来确定图形较优的放置顺序和放置位置。对于selection：常见有Firts-Fit、First-Fit-Dereasing/Increasing、Best-Fit。。。DJD1。。。主要思想是按照某一长度，面积，到达时间的顺序来确定放置顺序。对于placement，常见的有（Bottom-Left，尽量靠左下角摆放,Constructive Approac，放置进去所围成的矩形面积最小。。。。等）来衡量。【搜索算法】是在得到可行解的基础上，采用一些优化算法，调整样片的顺序，并不断探寻、迭代来寻找代价更低的放置顺序，常有tabu search、遗传算法、模拟退火算法、蚁群、粒子群等。。。。。
what is nfp?
定义
NFP是来确定两个图形位置关系的而一种方法。通过固定A，让B绕着A（touch but no intersection）旋转一周，其中B的相对位置不能发生改变，这样B的某一参考点形成的图形就是nfp，记作NFP(AB)。
用法
判断时，选取该参考点，若参考点在NFP内，则两图形相交；若在NFP上，则两图形相接触；若在NFP外，则两图形no intersection。
评价
NFP的方法：主要适合不允许/允许少量旋转角度的排样。因为nfp的数量会随角度的变化成指数增长，加大运算代价。
why nfp?
对比：NFP VS trigonometry approaches
nfp比传统的三角学会快好几倍，因为在处理nesting问题中：
- nesting是需要不断迭代，针对每一次迭代，sti方法都要进行一次计算，而NFP可以利用之前保存的结果。
- 每一次判断两个形状的位置情况，tri需要计算多边形中每个顶点与边之间距离，来判断关系，而npf方法只需要计算一次ref点和nfp图形t的位置关系。
- 对于消除重叠，tri需要在移动之后，再次计算以确定是否还有可移动的余地，nfp则可以一次在一个维度上移动到touch。
- 当多边形的边数增加时，图形更复杂，npf的优势更加明显
传统trigonometry方法
根据点、边的关系，来计算可以移动的距离。分为line-line、line-arc、arc-arc、arc-line四种情况，不同的情况计算方法有一定的差别。主要用到：做垂线，平移、做切线、找切点、平移相交点等。（真的是太复杂啦，有些公式步骤还没看懂！）
how to build nfp?
双凸图形（convex shapes）
- A逆时针绕边，B顺时针绕边
- 移至同一点
- 逆时针连接这些点
非凸图形（non-convex shapes）
- Digitisation 数字化：用离散的点（0-1）来表示图形，点上的值表示向右平移到白格的距离。
劣：分辨率的选择对结果影响很大，分辨率大，计算量大；分辨率小，不准确。
优：可以表示包含孔，互锁等的复杂图形 - Decomposition 分解：将非凸分解成很多小的凸形状（convex piceces,star-shaped polygons,Phi-function…，）分别求NFP之后再组合。
劣：分成的小块越多，时间成本越高 - Minkowski sums【不懂？闵可夫斯基？？】
-
Orbital sliding approach：固定A，通过touch but no intersection的方式旋转B，B上的参考点所形成的运动轨迹。
旋转法——NFP具体构建步骤
- 将B移动到与A相互touch的位置
- 将B绕A旋转一周
a.Detection of touching edges
b.Creation of potential translation vectors
c. Finding a feasible translation vector
d.Trimming the feasible translation vector
f.Applying the feasible translation vector
3. 只用前面两个步骤，难以处理图形带孔、存在互锁、精确契合、可拼接碎片的形状，又引入__Start points__的方法。通过初始点的确定，可以在一定程度上解决这个问题。参考论文2【有点复杂，需要时再查。】下图只是做一个例子看看，便于回忆。
Tips
- These datasets can be found on the EURO Special Interest Group on
Cutting and Packing (ESICUP) website3(摘抄自论文，可以从这个地方去找到一些用于实验/测试的数据。)
自我总结
【2019-10-18】第一次通博客来记录自己所学习的内容。
很多时候碎片式学习，导致看的东西太多太杂，无法将知识连贯起来，特别缺乏对内容从宏观上把握。突然发现写学习笔记，对于我这种"看过"真的只是="看过"的人来说，真的是个很不错的帮助自己理解的学习方法，哈哈哈！