分区加权Voronoi图的生成及其面积计算

摘要

Voronoi图是计算几何的一个重要分支,它在计算几何理论和应用中发挥着重要作用.该文所作的工作是:首先,在Voronoi图已有的理论基础之上,将加权Voronoi图扩展到分区加权Voronoi图,给出了分区加权Voronoi图的定义、性质和定理及相关证明;其次,分析了分区加权Voronoi图中的各种区域,并给出了一种计算相应区域面积的算法;再次,利用分区加权Voronoi图模拟石家庄市部分城区中的基站建设情况,并对模拟产生的重复覆盖、服务区和盲区面积进行了计算;最后,对该文所涉及到的算法,给出了用Visual C++语言实现的主要源程序.

目录

摘要

Abstract

第一章绪论

1.1计算几何与Voronoi图

1.2论文的研究内容

1.3论文的结构安排

第二章Voronoi图

2.1 Voronoi图的定义及其基本性质

2.2加权Voronoi图的定义及其基本性质

第三章分区加权Voronoi图

3.1分区加权Voronoi图的定义

3.2分区加权Voronoi图的基本性质

第四章分区加权Voronoi图的生成

4.1算法的基本思想

4.2算法描述

4.3算法中应注意的几个问题

4.3.1扇区的划分

4.3.2分区加权Voronoi图边界的近似抽出

4.3.3 Voronoi区域涂满与否的判定

4.4图例

第五章分区加权Voronoi图中的面积计算

5.1算法的基本思想

5.2算法描述

5.3算法分析及其应用实例

第六章实际应用举例

6.1分区加权Voronoi图应用举例

6.2应用前景展望

第七章结束语

致谢

参考文献

附录