启发式开料算法.docx

1
开料介绍以及启发式算法研究
目前针对pcb行业没有存在可以异形拼版的软件。但是有部分软件可以满足此功能都是应用在其他的行业，如果钢材切割，玻璃。五金之类的行业，这个些行业与pcb的拼版要求有很多工艺上的不一致。比如在钢材比较注重用已排拼板和新排拼板形成的凸包面积来确定评估标准
根据上述分析，我们认为自动拼板过程主要解决三个问题：一是新拼板的排放问题；一是状态评估问题；三是整理和后续准备问题•为此我们围绕这三个问题设计的自动拼板图形学算法有：
⑴，将新零件沿合成多边形的边界移动，以便对移动的每一位置作出状态评估，选出最优位置.
⑵，作为排料排放位置优劣的评估依据.
⑶合成多边形算法•求处于最佳位置和方向的新拼板和已排拼板以及原料边界的台成多边形，这是下一个拼板排放移动的基准.
详细分析：
初始化
针对目前板的外形等做些处理，减少在后续算法的复杂度
移动算法
由于移动算法在拼板中应用频率最高，，国外较为广泛使用是临界多边形法•待排多边形B不改变方向地靠接但不重叠已排区域（多边形）绕行一圈，，但A，B中只要有一个是凹多边形，在绕行时就可能出现A，B重叠的现象,
因此，每移动一步都要作重叠判断•同时，这种事后的重叠判断给移动的步长选取带来了盲目性，且步长不宜过大•对无需重叠判断的情况(两个凸多边形)，临界多边形法的算法复杂度只是
4
O(M+W),其中M・N为A,B的边数•而对需要进行重叠判断的情况，每次判断的复杂度为O(MXW)•临界多边形算法的复杂度为O((+W)XMN)•如果能得到图形学的一些结果作为先验知识，事先求出一次移动不发生重叠的最佳步长，它可以省略多边形A,B重叠的事后判断•大幅度提高算法的效率•目前有关的图形学结论的基本特征是考虑了A,B的边的某些特征在多边形靠接过程中的作用.
定义1•对一任意的N边形，可以用N个按逆时针顺序排列的顶点集合S,其中y>Y・在集合s中，存在点序列V={VK(XK,YK),?,VL(XL,YL)),如果，1<K<L<N,且Y都是递增，则称由点序列V组成的一组线段为沿轴的递增线段族；如果1<K<L<N,且Y都是递减，则称由点序列组成的一组线段为沿轴的递减线段族.
命题•根据定义，若多边形A和B满足移动条件，则多边形B沿x轴移动与多边形相接触的部分为B的递增线段族的顶点，或线段与的递减线段族的顶点或线段之间的接触•这样一来，只需计算出单调线族的点到边距离，就可得出每次移动的最佳步长.
算法1_
根据多边形A,B初始位置判断多边形B沿A边或B边移动的方向形成角度X,并计算出移动边的边长.
判断B沿形成的角度移动满足接触条件的递增线段的所有顶点，计算出这些顶点到A的递减线段族的线段的距离。
判别A的满足接触条件的递减线段族的所有顶点，计算出这些顶点到B的递增线段族的线段的距离
⑷从中选出最小的距离作为移动的步长；将B移动到新位置
算法1实际上给出的是多边形从一个顶点移动到另一个顶点的距离，即B沿A(B)的一条