学位论文 > 优秀研究生学位论文题录展示
一种任意多边形的裁剪算法
作 者: 白晨
导 师: 姚兴苗;潘国瑞
学 校: 电子科技大学
专 业: 软件工程
关键词: 任意多边形 裁剪 计算机图形学 算法
分类号: TP391.41
类 型: 硕士论文
年 份: 2010年
下 载: 118次
引 用: 0次
阅 读: 论文下载
内容摘要
线段裁剪和多边形裁剪作为图形裁剪中最基础、最常用的操作之一,其算法始终是计算机图形学研究的热点。近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。本文首先对目前国外经典线段裁剪和多边形裁剪算法作了概述,介绍了Cohen-Sutherland裁剪算法、直线段的中点分割裁剪算法、Liang-barsky算法、Sutherland-Hodgman算法,Weiler-Atherton算法的基本思路,也描述了国内在相关领域提出的一些典型算法,如刘勇奎、蔡志杰等人在Weiler-Atherton算法基础上提出的改进算法。接着,本文对现有算法的适用性进行了比较,重点分析了Weiler-Atherton算法。在此基础上,通过对多边形按照指定顶点顺序正向和逆向遍历,查找出全部最小多边形,再通过位置判断来得出最终裁剪结果多边形的算法进行了描述。随后,以伪代码和流程图的形式,进一步说明了该算法的结构。最后,根据算法特征,显然较适用于地质构图和地图比较算法。本文以地层结果图的绘制为例,用折线和多边形裁剪的算法,推断了地层逐条裁剪构图的过程,证明了该算法在处理此类运算时,算法计算量较小,时间较快,结果正确。本文又通过对有湖心岛的湖泊面积进行对比,用两个有环多边形之间的裁剪算法,推断了不并列且互不包含的两个带环多边形的裁剪步骤,证明了该算法不但裁剪结果正确,而且每个结果多边形在裁剪前包含于哪个多边形的属性可以得到准确描述,非常利于裁剪结果的再处理,比如分层染色。从而通过以上两个工程模拟背景,验证了算法的有效性。
|
全文目录
摘要 4-5 ABSTRACT 5-8 第一章 引言 8-12 1.1 课题背景 8-9 1.1.1 课题的目的 8 1.1.2 课题的意义 8 1.1.3 现实需求 8-9 1.2 国内外研究情况综述 9-10 1.3 本文的主要工作和研究内容 10-12 第二章 二维裁剪的基本原理 12-21 2.1 二维裁剪概念 12-14 2.2 常用的直线段裁剪算法 14-17 2.2.1 Cohen-Sutherland 裁剪算法 14-15 2.2.2 直线段的中点分割裁剪算法 15-16 2.2.3 Liang-barsky 算法 16-17 2.3 常用的多边形裁剪算法 17-20 2.3.1 Sutherland-Hodgman 逐边裁剪算法 17-19 2.3.2 Weiler-Atherton 双边裁剪算法 19-20 2.4 小结 20-21 第三章 任意多边形之间的裁剪算法 21-29 3.1 算法基本原理 21-29 3.1.1 不带环多边形之间的裁剪过程 21-26 3.1.2 带环多边形之间的裁剪过程 26-29 第四章 软件设计及实现 29-52 4.1 软件需求 29 4.2 类的描述和实现 29-32 4.3 设计流程图 32-39 4.4 伪代码实现 39-52 第五章 算法测试及实例 52-64 5.1 多边形与折线裁剪在地层结构图绘制中的应用方向 52-58 5.2 两个带环多边形间裁剪在湖泊面积比对中的应用方向 58-64 第六章 结论 64-65 致谢 65-66 参考文献 66-67
|
相似论文
- 基于差分进化算法的JSP环境下成套订单研究,F273
- 基于图的标志SNP位点选择算法研究,Q78
- 高灵敏度GNSS软件接收机的同步技术研究与实现,P228.4
- 天然气脱酸性气体过程中物性研究及数据处理,TE644
- 基于Thermo-Calc三元共晶合金凝固路径的耦合计算,TG111.4
- 压气机优化平台建立与跨音速压气机气动优化设计,TH45
- 多导弹协同作战突防效能评估及组合优化算法研究,TJ760.1
- 基于感性负载的车身网络控制系统,U463.6
- 基于蚁群算法的电梯群优化控制研究,TU857
- 高精度激光跟踪装置闭环控制若干关键问题研究,TN249
- 半导体激光器热电控制技术研究,TN248.4
- AES算法及其DSP实现,TN918.1
- 基于UWB脉冲信号的测距定位技术,TN929.5
- 基于TS101的DFT输出子集算法研究及软件实现,TN911.72
- 高光谱图像空—谱协同超分辨处理研究,TN911.73
- DBF接收机用于二维测向算法的研究,TN851
- 电视制导系统中视频图像压缩优化设计及实现研究,TN919.81
- IEEE802.16e信道编译码算法研究,TN911.22
- LDPC码译码算法的研究,TN911.22
- 频繁图结构并行挖掘算法的研究与实现,TP311.13
- 基于人眼检测的驾驶员疲劳状态识别技术,TP391.41
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理(信息加工) > 模式识别与装置 > 图像识别及其装置
© 2012 www.xueweilunwen.com
|