允许自由旋转的2个简单多边形匹配算法

为了解决二维不规则排料问题中的匹配问题,提出了一种允许自由旋转条件下,2个无孔洞的简单多边形之间的匹配算法.该算法基于2个多边形可以自由旋转的假设,对它们之间NFP为凹或凸的情况,选择适当的匹配方法,找出一种使得其匹配后空隙尽可能小,同时保证其整体的矩形的规整度也较高的匹配方案;并用匹配空隙的利用率、匹配后整体面积的利用率,以及匹配后整体的矩形规整度等多个指标来衡量匹配的效果.实验选择于ESICUP中的部分代表性的多边形样例与多个算法进行对比实验,结果表明,该算法在任意旋转精度的要求下,均具有运行速度快的特点,可以很好地应用于服装排料等实际问题.

An Algorithm for Matching Two Simple Polygons with Free Rotation

In order to solve the matching problem in two-dimensional irregular packing problem, an algorithm for matching two simple polygons without holes under the condition of free rotation is proposed. Based on the assumption that the two polygons can rotate freely, the algorithm chooses the appropriate matching method for the case of concave or convex NFP of the two polygons, and finds out a matching scheme that makes the space of the matched polygons as small as possible and ensures the overall rectangular regularity of the matched polygons as high as possible. Utilization ratio and rectangular regularity of the whole matched object are used to measure the matching effect. Some representative polygon samples in ESICUP are selected to compare with several algorithms. Under the requirement of arbitrary rotation accuracy, the algorithm is fast, which makes it suitable for practical problems such as packing problem.