平面内任意多边形简单划分的叠置算法研究

论文摘要

计算几何是计算机理论科学的一个新的极有生命力的研究领域,该学科已经有了巨大的发展并且产生了一系列的理论成果,在理论和应用上都具有十分重要的意义,叠置算法是计算几何研究领域当中的一个分支,其研究成果已在动态仿真、机器人学、地理信息系统等许多领域中得到了广泛的应用,尤其在机器人学领域,它是利用Minkowski和计算机器人无碰撞路径过程中的重要步骤。因此,如何准确地为机器人计算出无障碍的路径,一直是国内外学者研究的重要课题。首先,叠置算法是计算两个多面体Minkowski和的重要步骤,计算线段之间的交点是叠置的第一步。在对国内外研究现状进行综合分析的基础上,深入研究现有的线段求交算法。通过为图层赋予颜色属性,提出了基于平面扫描的线段求交算法,分析了算法的详细执行过程和算法的执行效率,并讨论了该算法在众多领域中的应用。其次,通过对现有的叠置算法的研究,发现一些算法存在不足之处,例如不能计算平面划分为凹多边形的叠置。为了克服现有叠置算法的缺陷,提高计算叠置的执行效率,通过引入广度优先遍历图的思想,本文提出了平面内任意多边形简单划分的叠置算法,算法可以计算平面内多边形任意简单划分的叠置。整个算法分为计算交点、拓扑重组和更新双向链接边表三步。再次,通过实例来展示了叠置算法的详细执行过程,并对算法的正确性和复杂度进行了分析。最后,通过详细的实验过程验证了本文的研究内容,通过与现有算法的对比,对实验结果进行了详细分析。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究意义
• 1.2 叠置算法的研究现状
• 1.3 叠置算法的应用
• 1.3.1 机器人路径规划
• 1.3.2 地理信息系统
• 1.4 本文研究内容
• 1.5 本文组织结构
• 第2章 理论基础
• 2.1 相关的几何定义
• 2.1.1 欧几里德空间
• 2.1.2 点
• 2.1.3 直线与线段
• 2.1.4 矢量及其加减法
• 2.1.5 多边形
• 2.1.6 多面体
• 2.1.7 平面划分图
• 2.2 基础知识及内容
• 2.2.1 Minkowski 和的定义
• 2.2.2 Minkowski 和的基本性质
• 2.2.3 边界表示方法
• 2.2.4 三角剖分
• 2.3 数据结构与算法
• 2.3.1 数据结构
• 2.3.2 算法
• 2.4 本章小结
• 第3章 基于平面扫描的线段求交算法研究
• 3.1 引言
• 3.2 相关定义
• 3.3 基于平面扫描的线段求交算法
• 3.3.1 平面扫描算法的基本思想
• 3.3.2 平面扫描算法的定义
• 3.3.3 事件队列
• 3.3.4 算法的状态及其维护
• 3.4 算法的流程图
• 3.5 算法描述
• 3.6 算法的正确性分析
• 3.7 算法的复杂度分析
• 3.7.1 算法的时间复杂度分析
• 3.7.2 算法的空间复杂度分析
• 3.8 本章小结
• 第4章 平面内任意多边形简单划分的叠置算法
• 4.1 引言
• 4.2 相关辅助定义
• 4.3 叠置算法的基本思想
• 4.4 DCEL 双向链接边表
• 4.4.1 半边表示方法
• 4.4.2 双向链接边表
• 4.5 平面内任意多边形简单划分的叠置算法
• 4.5.1 拓扑重组
• 4.5.2 算法描述
• 4.5.3 实例分析
• 4.5.4 更新双向链接边表
• 4.6 算法的正确性分析
• 4.6.1 拓扑重组的正确性
• 4.6.2 更新双向链接边表的正确性
• 4.7 算法的复杂度分析
• 4.7.1 算法的时间复杂度分析
• 4.7.2 算法的空间复杂度分析
• 4.8 本章小结
• 第5章 实验与分析
• 5.1 实验环境设置
• 5.2 OpenGL 简介
• 5.3 C#和OpenGL 开发环境的建立
• 5.4 实验及结果分析
• 5.4.1 实验数据的设置
• 5.4.2 基于平面扫描的线段求交算法的实现
• 5.4.3 叠置算法的实验流程
• 5.4.4 实验结果分析
• 5.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间承担的科研任务与主要成果
• 致谢
• 作者简介