Link-2可视多边形中三守卫问题的求解算法研究

摘要

本文针对三个守卫(three-guard)问题进行研究，该问题可描述为:给定平面上一个简单多边形P，以及P边界上的两点s和t（分别作为起始点和终点）。点s和t将多边形边界分割成两条边界链L和R。三个守卫按从s到t的方向移动，协同完成对P的扫描，并最终将可能的入侵者从t点驱逐出去。要求两守卫分别沿L链和R链移动，第三个守卫可在P内部或P的边界上移动，且在移动过程中相邻守卫要时刻保持相互可见。
　　论文首先论述了计算几何领域中的几个经典问题，然后在论述相关理论知识的基础上，着重研究了三个守卫问题的扫描机理。为解决三个守卫的扫描问题，详细分析了two-guard问题的求解思路，通过分析three-guard问题与two-guard问题求解方案中移动操作对应约束条件，在引入link-2可视和link-2射点等概念的基础上，提出了判断给定简单多边形是否为三个守卫可扫描的多边形的充分必要条件，并在三个守卫可扫描的前提下，论述了具体扫描方案的构造过程。本文提出的算法能够在O(nlogn)时间复杂度内判定出给定的多边形是否为三个守卫可扫描的，并能在O(nlogn+m)时间复杂度内构造出具体扫描方案，其中n表示多边形P的顶点个数，m（≤n2）是构造扫描方案的扫描规则的数量。该结果改进了已有时间复杂度分别为O(n2)和O(n2logn)的算法。在理论分析的基础上，构造数据结构，具体实现了所设计的算法。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 国内外的研究现状

1．3 主要研究内容

1．4 论文的组织结构

第2章 求解Three-guard问题的相关基础

2．1 计算几何中的几个经典问题

2．1．1 计算几何学

2．1．2 艺术画廊问题

2．1．3 最短巡视员路径问题

2．1．4 Two-guard问题

2．2 Three-guard问题

2．3 预备知识

2．3．1 基本定义

2．3．2 两个守卫可扫描多边形

2．3．3 Link-2弱可视性

2．3．4 Link-2射点

2．3．5 Link-2死锁和link-2楔形

第3章 Three-guard问题求解分析

3．1 Three-guard可扫描性的判定

3．1．1 Link-2弱可视性的判定

3．1．2 Link-2死锁和link-2楔形的判定

3．2 Three-guard扫描方案的构造

3．2．1 直扫描规则

3．2．2 一般扫描

第4章 Three-guard问题求解算法的实现

4．1 基本数据结构

4．1．1 顶点的数据结构

4．1．2 线段的数据结构

4．2 几个关键问题的算法实现

4．2．1 Link-2射点的计算

4．2．2 查找link-2死锁

4．2．3 查找最大厅link-2楔形

4．2．4 直扫描具体扫描方案

4．2．5 反扫描具体扫描方案

4．3 两种扫描情形的算法实现

4．3．1 直扫描算法

4．3．2 一般扫描

第5章 运行结果及分析

5．1 运行结果

5．2 算法分析

5．2．1 时间复杂度分析

5．2．2 空间复杂度分析

5．2．3 扫描总路程分析

第6章 总结与展望

6．1 工作总结

6．2 进一步的研究展望

参考文献

致谢

作者简介