学位论文 > 优秀研究生学位论文题录展示

基于Minkowski Sum的优化排样算法的研究和实现

作　者: 华焱
导　师: 陈文亮
学　校: 南京航空航天大学
专　业: 航空宇航制造工程
关键词: 排样 Minkowski Sum 三角剖分 多边形的并 CAD
分类号: TB114.1
类　型: 硕士论文
年　份: 2007年
下　载: 139次
引　用: 1次
阅　读: 论文下载
 

内容摘要


二维零件的优化排样问题广泛的存在于飞机、汽车、轮船等机械制造行业领域中。传统的排样过程,从产品设计、展开计算到下料排样是由有经验的技师凭借人工经验,直觉和想象力进行判断和试验,虽然能取得较好的成绩,但是随着零件形状复杂度的提升,其周期拉长,劳动强度也大大增加,并且很难取得最优解。随着CAD技术的日益成熟,利用计算机进行辅助优化自动排样具有非常重要的意义。本文在广泛调研的基础上,结合国内外的研究现状和排样问题的自身特点,对具有二维复杂形状的零件的排样问题进行了深入的研究,内容主要包括如下:设计并实现了一套表达排样零件的数据结构及相关算法。它采用双向链表结构,能表达任意的二维复杂多边形,支持删除、插入节点等操作,能高效的支持排样算法所需要的拓扑信息的查询、遍历等操作。提出了一种求解凹多边形的Minkowski Sum的高效算法。由于直接求解两个凹多边形的Minkowski Sum比较复杂,该算法提出先将凹多边形作三角剖分,然后对三角形进行求解Minkowski Sum,最后将求得的Minkowski Sum取其并集,将求解两个凹多边形的问题转化为求解两个三角形的Minkowski Sum问题,并加以理论证明,简单高效地解决了这一问题。引入了一种基于Minkowski Sum的高效排样算法,该算法先求出两个任意多边形Minkowski Sum,再基于所求得的Minkowski Sum边界不同的位置合并出一个多边形,然后对合并后的多边形求其Minkowski Sum,并作单排最优解处理,循环上述步骤,直至逼近全局最优解。此算法能够处理各种复杂形状的多边形(包括凹多边形),生成结果时间周期较短,可取得理想效果。在上述技术研究的基础上,作者采用C++实现了一种基于Minkowski Sum的高效优化排样系统,经实例验证,该系统具有高速、高效等特点。

全文目录


摘要  4-5
ABSTRACT  5-10
1 第一章 绪论  10-17
  1.1 引言  10
  1.2 排样问题概述  10-11
  1.3 排样技术发展概况  11-15
    1.3.1 国外研究状况  11-13
    1.3.2 国内研究状况  13-14
    1.3.3 排样技术研究的关键问题  14-15
  1.4 本文研究重点  15
  1.5 本文章节安排  15-17
2 第二章 排样算法的主要概念和相关知识  17-28
  2.1 排样和排样的分类  17-18
    2.1.1 优化排样  17
    2.1.2 排样的分类  17-18
  2.2 计算几何知识概念  18-26
    2.2.1 Minkowski Sum 及其算法  18-21
    2.2.2 多边形三角剖分  21-24
    2.2.3 双向链接边表  24-25
    2.2.4 多边形的并  25-26
  2.3 材料利用率的计算  26-27
  2.4 本章小结  27-28
3 第三章 基于MINKOWSKI SUM 的优化排样算法  28-39
  3.1 排样算法步骤  28-29
  3.2 数据结构及算法的关键技术  29-37
    3.2.1 任意多边形的表示  29
    3.2.2 Minkowski Sum 的求解算法  29-32
    3.2.3 关键点选取和多边形合成方法  32-33
    3.2.4 单排排样的求解  33-37
    3.2.5 循环优化求解  37
  3.3 本章小结  37-39
4 第四章 优化排样系统的实现  39-57
  4.1 排样系统实现的途径  39-44
    4.1.1 排样系统软件技术途径  39-40
    4.1.2 排样系统开发平台的确定  40-44
  4.2 排样系统设计  44-52
    4.2.1 排样系统的总体流程图  44-47
    4.2.2 排样系统的功能和结构设计  47-49
    4.2.3 排样系统的开发  49-52
  4.3 应用实例  52-55
  4.4 本算法的优缺点分析  55-56
  4.5 本章小结  56-57
5 第五章 总结与展望  57-59
  5.1 全文总结  57-58
  5.2 研究展望  58-59
参考文献  59-64
致谢  64-65
攻读硕士学位期间发表的论文情况  65

相似论文

  1. 基于约束图的服装参数化制板技术,TS941.2
  2. 船用柴油机关键件CAD/CAPP/CAM集成系统开发,U664.121
  3. 面向肺部CAD的特征提取、选择及分类方法研究,TP391.41
  4. 铸造工艺CAD软件开发,TP391.72
  5. 一种支持异源系统协同设计的CAD数据集成方法,TP391.72
  6. 基于SolidWorks的板料成形仿真后置处理系统的开发,TP391.72
  7. 基于Pro/E的钣金件毛坯展开仿真系统研究,TG38
  8. 基于SolidWorks的板料成形快速仿真系统的研究和开发,TG385
  9. 基于Open Inventor的圈绒地毯花型仿真技术研究,TS106.76
  10. 基于Pro/E的三维零件参数化建模和特征提取研究,TP391.72
  11. 基于数学形态学的层次性形状分解,TP391.41
  12. 船体分段的机器人焊接路径规划与离线编程,TP242
  13. 基于PRO/E的棒材二辊矫直机辊型设计与制造,TG333.23
  14. CAD/FEA无缝集成平台CAFIP的设计与研发,TP391.72
  15. 跨平台模具CAD系统研究与应用,TP391.72
  16. 基于OSG的三维不规则军标地形匹配应用研究,E919
  17. 基于数据挖掘的三维模型表征、索引与检索研究,TP391.3
  18. 服装CAD牛仔裤样板设计与快速生成研究,TS941.2
  19. 交互式局部约束织物纹理映射技术的研究与实现,TP391.41
  20. CAD测试图档日志分析及其错误标示自动判别技术研究,TP391.7
  21. 冲压模具用零部件智能CAD系统的研究与开发,TP391.72

中图分类: > 工业技术 > 一般工业技术 > 工程基础科学 > 工程数学 > 概率论、数理统计的应用 > 运筹学的应用
© 2012 www.xueweilunwen.com