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

An Algorithm for Matching Two Simple Polygons with Free Rotation

作　　者：刘新阳 雍俊海[1,2,3] Liu Xinyang;Yong Junhai(School of Software,Tsinghua University,Beijing 100084;Key Laboratory for Information System Security,Ministry of Education of China,Beijing 100084;Beijing National Research Center for Information Science and Technology,Beijing 100084)

机构地区：[1]清华大学软件学院,北京100084 [2]信息系统安全教育部重点实验室,北京100084 [3]北京信息科学与技术国家研究中心,北京100084

出　　处：《计算机辅助设计与图形学学报》2020年第3期486-492,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61672307,61562063).

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

关 键 词：多边形匹配 自由旋转 排料问题 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]