单一多边形的优化排样问题

摘要

本文首先介绍1种单1多边形在矩形板材上的排样算法。以常见排样方式中最典型的对头双排为例分析板材2维排样的整体优化问题，结合余料的利用，建立2维排样整体优化的合理数学模型。利用改进的平行线分割1步平移排样算法，结合冲裁件外轮廓曲线，分析计算模型中的未知排样参数，并给出了与整体优化模型相匹配的整体优化排样算法。算法能够根据板材和冲裁件的图形信息快速、自动地确定板材2维排样整体优化的排样参数，由此得到1个在板材上排放最多可冲裁0件的优化排样方案。
    在单1多边形排样算法研究的基础上，结合计算机图形学知识，进1步提出1种基于扫描区间几何表示方法的启发式定位算法。排样对象用等距扫描区间进行表示，利用启发式算法可以把复杂的多边形判交与定位问题转化为扫描区间之间的x坐标值的简单判断，算法的计算复杂度与排样多边形的几何形状无关。在排样多边形的排样次序和旋转角度已经确定的情况下，利用该算法可以自动、高效地实现多边形在板料上紧密排列。

关键词: 排样；单1冲裁件；冲裁步距；自动排样优化；嵌套排样；启发式算法。

Abstract

This article first introduces one kind of sole polygon on the rectangular plate platoon type algorithm. Take the common platoon quadrat in the formula most typical enemy two-row as the example analysis plate two-dimensional platoon type whole optimization question, unifies Yu Liao the use, establishes reasonable mathematical model which the two-dimensional platoon type whole optimizes. Divides using the improvement parallel line one step displaces evenly the type algorithm, outside the union blanking outline curve, in the analysis computation model unknown platoon type parameter, and gave the whole which matched with the whole optimization model to optimize the row of type algorithm. The algorithm can according to the plate and the blanking graph information fast, determined automatically the plate two-dimensional platoon type whole optimizes the platoon type parameter, obtains one to discharge most much from this on the plate may the blanking components optimized row of type plan. （科教作文网http://zw.ΝsΕac.cOM编辑）
In the sole polygon row of type algorithm research foundation, unifies the computer graphics knowledge, further proposes one kind based on the scanning sector geometry expression method heuristic localization algorithm. The row of type object carries on the expression with the equal-space scanning sector, uses the heuristic algorithm to be possible to sentence the complex polygon delivers the localization question to transform as the scanning sector between x coordinate figure simple judgment, the algorithm computation order of complexity has nothing to do with with the row of type polygon geometry shape. Already determined in the row of type polygon platoon type order and the degrees rotation in the situation, used this algorithm to be possible automatic, to realize the polygon to be closely packed highly effective on the sheet.

Key word : Row of type; Sole blanking; Blanking step of distance; Automatic platoon type optimization; Nesting row of type; Heuristic algorithm.