计算几何中LR可视化问题研究

论文摘要

LR可视化问题是计算几何领域的重要研究课题,也是计算几何领域经典应用问题的基础研究课题,利用对简单多边形的LR可视特性的判断,能够帮助人们得到求解这些经典问题的有效算法。因此,针对LR可视多边形的研究,不仅具有理论研究意义,而且也有十分重大的实际应用价值。本文在论述简单多边形分割的相关理论的基础上,对LR可视多边形的特征及其判断等问题进行了深入的研究,给出了判别一个简单多边形是否为LR可视多边形的充分必要条件,并加以严格证明。在此基础上,依据LR可视多边形成立的充分必要条件,给出了判别一个给定简单多边形是否LR可视多边形的算法描述,并对算法的时间性能做了分析。结果表明,本文所给出的算法,比经典的利用最短路径树的生成的判别算法更加简单、实用,其时间复杂度是线性的。作为LR可视化多边形的应用实例,本文还对画廊问题、巡视员路径等问题,以及如何利用LR可视多边性的特性来降低求解这些问题的复杂性,提高求解精度等内容,做了较为详尽的论述。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景与研究意义
• 1.2 国内外的研究现状
• 1.3 研究内容
• 1.4 本文的组织结构
• 第2章 LR可视化问题的相关理论基础
• 2.1 计算几何学及其应用领域
• 2.2 LR可视化问题描述
• 2.2.1 简单多边形
• 2.2.2 简单多边形的分割
• 2.2.3 component
• 2.2.4 必要分割与非必要分割
• 2.2.5 可视性问题
• 2.2.6 LR可视多边形
• 第3章 LR可视多边形的判定问题
• 3.1 LR可视多边形的特征
• 3.2 非LR可视多边形的必要条件
• 3.3 判别LR可视多边形的充分条件
• 第4章 LR可视多边形的判别算法
• 4.1 基于最短路径树（SPT）的判别算法
• 4.1.1 算法思想
• 4.1.2 算法描述
• 4.1.3 算法分析
• 4.2 基于LR可视多边形特征的判别算法
• 4.2.1 算法思想
• 4.2.2 算法描述
• 4.2.3 算法分析
• 第5章 LR可视多边形的应用研究
• 5.1 画廊问题
• 5.2 最短巡视员路径问题
• 5.3 m-巡视员路径问题
• 5.4 LR可视多边形的利用原则
• 第6章 总结
• 6.1 论文工作总结
• 6.2 进一步研究工作
• 参考文献
• 致谢
• 研究生履历