用于二维不规则排样的离散临界多边形模型  

Discrete No-Fit Polygon,A Simple Structure for the 2-D Irregular Packing Problem

作　　者：张德富[1,2] 陈竞驰[1] 刘永凯[1] 陈火旺[2,3] 

机构地区：[1]厦门大学计算机科学系,福建厦门361005 [2]东南融通博士后工作站,福建厦门361005 [3]国防科学技术大学计算机学院,湖南长沙410073

出　　处：《软件学报》2009年第6期1511-1520,共10页Journal of Software

基　　金：国家自然科学基金No.60773126;福建省自然科学基金No.A07100234;厦门大学985二期信息科技基金No.0000-X07204;厦门大学院士启动基金No.X01109~~

摘　　要：提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.This paper presents a model based on discrete no-fit polygon for the two-dimensional irregular packing problem. Burke et al. have presented an effective BLF algorithm to solve the irregular packing problem, however, their algorithm might generate invalid results for Some special cases. To solve this problem, a model based on discrete no-fit polygon is proposed, and its correctness has been strictly proved. Only points and intervals are only considered by this model, which greatly decreases the geometry complexity of the original problem and makes the problem easily solved by many heuristic strategies. Computational results show that the algorithm based on discrete no-fit polygon model is very efficient.

关 键 词：不规则排样问题 禁止区 临界多边形 离散临界多边形 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]