| 摘要 | 第5-6页 |
| ABSTRACT | 第6页 |
| 第1章 绪论 | 第9-14页 |
| 1.1 研究背景及意义 | 第9-10页 |
| 1.2 国内外的研究现状 | 第10-12页 |
| 1.3 主要研究内容 | 第12页 |
| 1.4 论文的组织结构 | 第12-14页 |
| 第2章 求解Three-guard问题的相关基础 | 第14-32页 |
| 2.1 计算几何中的几个经典问题 | 第14-19页 |
| 2.1.1 计算几何学 | 第14-15页 |
| 2.1.2 艺术画廊问题 | 第15-16页 |
| 2.1.3 最短巡视员路径问题 | 第16-17页 |
| 2.1.4 Two-guard问题 | 第17-19页 |
| 2.2 Three-guard问题 | 第19-20页 |
| 2.3 预备知识 | 第20-32页 |
| 2.3.1 基本定义 | 第20-26页 |
| 2.3.2 两个守卫可扫描多边形 | 第26-27页 |
| 2.3.3 Link-2弱可视性 | 第27-28页 |
| 2.3.4 Link-2射点 | 第28-30页 |
| 2.3.5 Link-2死锁和link-2楔形 | 第30-32页 |
| 第3章 Three-guard问题求解分析 | 第32-53页 |
| 3.1 Three-guard可扫描性的判定 | 第32-38页 |
| 3.1.1 Link-2弱可视性的判定 | 第33-35页 |
| 3.1.2 Link-2死锁和link-2楔形的判定 | 第35-38页 |
| 3.2 Three-guard扫描方案的构造 | 第38-53页 |
| 3.2.1 直扫描规则 | 第38-46页 |
| 3.2.2 一般扫描 | 第46-53页 |
| 第4章 Three-guard问题求解算法的实现 | 第53-68页 |
| 4.1 基本数据结构 | 第53-55页 |
| 4.1.1 顶点的数据结构 | 第53-54页 |
| 4.1.2 线段的数据结构 | 第54-55页 |
| 4.2 几个关键问题的算法实现 | 第55-63页 |
| 4.2.1 Link-2射点的计算 | 第55-56页 |
| 4.2.2 查找link-2死锁 | 第56-57页 |
| 4.2.3 查找最大link-2楔形 | 第57-59页 |
| 4.2.4 直扫描具体扫描方案 | 第59-61页 |
| 4.2.5 反扫描具体扫描方案 | 第61-63页 |
| 4.3 两种扫描情形的算法实现 | 第63-68页 |
| 4.3.1 直扫描算法 | 第63-65页 |
| 4.3.2 一般扫描 | 第65-68页 |
| 第5章 运行结果及分析 | 第68-72页 |
| 5.1 运行结果 | 第68-70页 |
| 5.2 算法分析 | 第70-72页 |
| 5.2.1 时间复杂度分析 | 第70-71页 |
| 5.2.2 空间复杂度分析 | 第71页 |
| 5.2.3 扫描总路程分析 | 第71-72页 |
| 第6章 总结与展望 | 第72-74页 |
| 6.1 工作总结 | 第72-73页 |
| 6.2 进一步的研究展望 | 第73-74页 |
| 参考文献 | 第74-78页 |
| 致谢 | 第78-79页 |
| 作者简介 | 第79页 |