| 本文已被：浏览 6006次 下载 9146次 |
码上扫一扫！ |
|
|
| 用于二维不规则排样的离散临界多边形模型 |
|
张德富1,2, 陈竞驰1, 刘永凯1, 陈火旺2,3
|
|
1.厦门大学 计算机科学系,福建 厦门 361005;2.东南融通博士后工作站,福建 厦门 361005;3.国防科学技术大学 计算机学院,湖南 长沙 410073
|
|
| 摘要: |
| 提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的. |
| 关键词: 不规则排样问题 禁止区 临界多边形 离散临界多边形 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.60773126 (国家自然科学基金); the Natural Science Foundation of Fujian Province of China under Grant No.A0710023 (福建省自然科学基金); the 985 Information Technology Fund of Xiamen University of China under Grant No.0000-X07204 (厦门大学985二期信息科技基金); the Academician Start-Up Fund of Xiamen University of China under Grant No.X01109 (厦门大学院士启动基金) |
|
| Discrete No-Fit Polygon, A Simple Structure for the 2-D Irregular Packing Problem |
|
ZHANG De-Fu,CHEN Jing-Chi,LIU Yong-Kai,CHEN Huo-Wang
|
| Abstract: |
| 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. |
| Key words: irregular packing problem infeasible interval no-fit polygon discrete no-fit polygon |
