基于轨迹计算的临界多边形求解算法  

New Algorithm for No Fit Polygon Calculation

作　　者：刘胡瑶[1] 何援军[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200030

出　　处：《计算机辅助设计与图形学学报》2006年第8期1123-1129,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60573146);国家"八六三"高技术研究发展计划(2003AA411310)

摘　　要：将多边形滑动碰撞问题转化为顶点和边之间的轨迹线提取问题,从而降低了时间复杂度,并可统一处理边界空腔和内部靠接临界多边形问题.该算法的基本原理是:1)求解多边形顶点相对于另一多边形的轨迹线;2)求解轨迹线集合所形成的外包多边形和内部顺时针环,得到的多边形即为临界多边形.该算法采用基于网格的线段索引方法来加快线段之间的求交计算,进一步提高了临界多边形求解的计算速度.In this paper, the problem of calculating movement of piece is simplified to the problem of finding track line segments between vertices and edges, hence the time complexity is much reduced, and special cases such as inner cavity and inner NFP （no fit polygon） can also be tackled. The main principles of this new approach are： 1） Find out the track line segments for vertices of one polygon to another polygon＇s edges; 2） Get the enclosing polygon and internal clockwise loops that was formed by the track line segments, finally the result polygons are the final NFPs. This new approach adopts a grid-based line index algorithm which can facilitate the calculation of intersection points for lines, hence the speed of calculating NFP is significantly increased.

关 键 词：临界多边形 轨迹线 线段索引 排样 

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