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

任意多边形的裁剪算法及其在土建工程中的应用

作　者: 李海姣
导　师: 张维锦
学　校: 华东交通大学
专　业: 结构工程
关键词: Visual C++ OpenGL 多边形裁剪算法新函数三维扣减
分类号: TU17
类　型: 硕士论文
年　份: 2005年
下　载: 215次
引　用: 1次
阅　读: 论文下载

内容摘要

裁剪算法是计算机图形学中的基本算法，也是其它诸多重要问题的基础。经过了近半个世纪的讨论和探索，一些线裁剪算法越来越完善，尤以矩形窗口的线裁剪方法最为突出，但一般多边形窗口的线裁剪算法并不是十分理想，而多边形窗口的多边形裁剪算法还没有受到广泛的关注。但后两者在图形学以及工程实际的应用中具有更为重大的现实意义。尤其是目前还没有文献提到带圆弧边的多边形的多边形裁剪问题。而这类问题又是土建工程三维可视化预算软件开发中最为基础的问题。因此，本文首先基于Visual C++6.0语言、采用OpenGL图形库，开发了一个小型矢量图形系统，为后续算法的设计、调试和应用提供了图形平台。接着，设计了一个任意多边形窗口的多边形裁剪算法。该算法不仅适用于一般意义上的凸多边形和凹多边形，而且还适用于带圆弧边的组合多边形以及有空洞的多边形(本文称之为广义多边形)。其次，在算法的设计中采用了包围盒技术、计算几何的跨立法、射线法等技术，大大简化了计算过程。再者，Visual C++支持的CArray类，以及CObList类的数据结构(单链表)的采用，大幅度地减少了内存开销，节约了存储空间。符号函数的引入，有效地控制了误差传递，确保了计算精度。最后，针对MFC(Microsoft Foundation Class Library)提供的库函数的不足，编写了一个判断点与广义多边形位置关系的新函数，有效地消除了由此产生的致命性错误。最终实现了一个几何适应性强，时间和空间复杂度低的算法。最后，将新算法应用于土建工程三维可视化预算软件中，成功地实现了三维动态交互绘制中墙与墙、墙与梁、墙与柱，以及墙与板的实时扣减。

全文目录

第一章绪论  11-17
  1.1 课题背景  11-12
    1.1.1 课题的意义  11
    1.1.2 发展现状  11
    1.1.3 现实需求  11-12
  1.2 国内外研究动向及研究水平  12-14
    1.2.1 矩形窗口线裁剪算法  12
    1.2.2 一般多边形窗口线裁剪算法  12-14
  1.3 本论文的主要研究工作  14-17
    1.3.1 论文研究的目的  14
    1.3.2 硬件平台和软件平台的选择  14-15
    1.3.3 系统开发的核心技术  15-16
    1.3.4 论文工作简介  16-17
第二章小型矢量图形系统设计  17-34
  2.1 矢量图形系统开发方法选择  17-19
    2.1.1 Visua1 C++语言选择  17-18
    2.1.2 OpenGL图形系统的选择  18-19
  2.2 功能和界面设计  19-22
    2.2.1 工具条说明  20
    2.2.2 基本操作  20-21
    2.2.3 功能简介  21-22
  2.3 基于文档-视图结构的类  22-25
    2.3.1 主窗口(CMainFrame)  23-24
    2.3.2 文档(CMyFrameDoc)类  24-25
    2.3.3 视图类(CMyFrameView)  25
  2.4 系统的总体结构  25-26
  2.5 系统类的层次结构设计  26-27
  2.6 系统类库结构的实现  27-32
    2.6.1 实现机理-多态性  27
    2.6.2 基本图元的实现  27-31
    2.6.3 多边形类的构建  31
    2.6.4 墙体类的实现构建  31-32
  2.7 系统数据结构  32-33
  2.8 本章小结  33-34
第三章多边形类的构建  34-46
  3.1 构建多边形类的意义  34
  3.2 数据结构  34-35
  3.3 多边形类的构造  35-37
    3.3.1 类的声明  35
    3.3.2 类的实现  35-37
    3.3.3 成员函数简介  37
  3.4 多边形的绘制  37-40
    3.4.1 多态性机制的应用  37
    3.4.2 复杂多边形的绘制  37-39
    3.4.3 多边形的绘制机理  39-40
  3.5 多边形的选中  40-41
  3.6 多边形面积计算  41-43
    3.6.1 算法思路  41-42
    3.6.2 源代码  42-43
  3.7 多边形绕向判定  43-45
    3.7.1 折线段拐向的判断方法  43
    3.7.2 多边形绕向判定  43-45
  3.8 本章小结  45-46
第四章计算几何中的裁剪算法  46-54
  4.1 裁剪算法定义及分类  46
    4.1.1 裁剪算法定义  46
    4.1.2 裁剪算法分类  46
  4.2 裁剪算法的执行过程  46-47
  4.3 线裁剪算法综述及经典算法不足分析  47-49
    4.3.1 凸多边形窗口的线裁剪算法  47-48
    4.3.2 凹多边形窗口的线裁剪算法  48-49
  4.4 多边形窗口的多边形裁剪算法综述及不足分析  49-52
    4.4.1 矩形窗口多边形裁剪算法  50-52
    4.4.2 一般多边形窗口的多边形裁剪算法  52
  4.5 综述  52
  4.6 本文算法的提出  52-54
第五章多边形裁剪算法  54-70
  5.1 算法简述  54-58
    5.1.1 基本概念与定义  54-55
    5.1.2 数据结构  55-56
    5.1.3 算法描述  56-58
  5.2 核心步骤的处理方法  58-65
    5.2.1 运用包围盒剔除不相交的边  59
    5.2.2 点与直线位置关系判定  59-60
    5.2.3 一个快速判断线段位置关系的算法  60-63
    5.2.4 射线法判断点是否在多边形内  63-64
    5.2.5 重合边界的处理  64
    5.2.6 交点的排序和裁剪后线段的显示  64-65
  5.3 算法比较  65-67
    5.3.1 空间复杂度比较  65-66
    5.3.2 时间复杂度比较  66-67
    5.3.3 本文算法的优点  67
  5.4 算例  67-70
第六章库函数 PtInRegion的替代  70-79
  6.1 库函数 BOOL PtInRegion(POINT point)简介  70-72
    6.1.1 函数原型  70
    6.1.2 函数功能  70-71
    6.1.3 函数使用的参数  71
    6.1.4 注意事项  71
    6.1.5 函数伪代码  71-72
  6.2 库函数存在问题分析  72
    6.2.1 数据类型  72
    6.2.2 适用范围有限、计算效率低  72
  6.3 函数int PInsideRgn(MyPoint p，int tag)简介  72-74
    6.3.1 射线法原理  72-73
    6.3.2 对函数的几点说明  73-74
    6.3.3 算法描述  74
  6.4 程序跟踪示例  74-77
  6.5 程序复杂度分析  77-78
  6.6 小结  78-79
第七章多边形裁剪的应用  79-84
  7.1 墙体扣减  79-82
    7.1.1 手工计算墙体的难点  79
    7.1.2 系统中的处理方法  79-82
  7.2 墙与柱子扣减  82-83
  7.3 柱与梁、柱与板的扣减  83-84
第八章结论  84-86
  8.1 任意多边形的多边形裁剪算法  84
  8.2 多边形裁剪算法在土建工程中的应用  84
  8.3 本文的创新点  84-85
    8.3.1 设计了一个多边形类  84
    8.3.2 提出了一个任意多边形的多边形裁剪算法  84
    8.3.3 设计了一个库函数的替代函数  84-85
  8.4 还有待进一步研究的问题  85-86
    8.4.1 系统功能有待于进一步增强  85
    8.4.2 内存泄漏的检测和消除  85
    8.4.3 数据结构设计能力有待于进一步提高  85-86
致谢  86-87
参考文献  87-90
个人简历在读期间发表的学术论文  90

任意多边形的裁剪算法及其在土建工程中的应用

内容摘要

全文目录

相似论文