线段加权Voronoi图的离散生成

摘要

线段加权Voronoi图是对普通Voronoi图在生成元以及权重两方面加以推广而产生的。本文给出了如何用离散的方法来生成线段加权Voronoi图。文章主要部分的基本思想框架是：首先，在Voronoi图已有的理论基础之上，将Voronoi图的生成元由点扩展到线段，即而给出了线段加权Voronoi图的定义；其次，给出线段加权Voronoi图离散生成法的基本思想，离散生成算法，关键技术并与已有算法进行比较和分析；再次，利用线段加权Voronoi图解决绿化问题和水域划分问题；最后，对本文所涉及到的算法，给出了用Visual C++语言实现的主要源程序。

目录

声明

摘要

第一章 绪论

1.1 Voronoi图简介

1.1.1 Voronoi图的产生背景

1.1.2 Voronoi图的研究现状

1.2 论文的研究内容

1.3 论文的组织结构

第二章 Voronoi图及其应用

2.1 Voronoi图

2.1.1 Voronoi图的定义

2.1.2 Voronoi图的基本性质

2.2 Voronoi图的应用

第三章 Voronoi图的几种主要生成算法

3.1 构造Voronoi图的经典传统算法

3.2 Voronoi图的离散构造算法

3.2.1 离散Voronoi图的定义

3.2.2 离散Voronoi图的性质

3.2.3 离散Voronoi图的画法

第四章 线段加权Voronoi图的离散生成

4.1 加权Voronoi图

4.1.1 点生成元加权的Voronoi图

4.1.2 线段加权的Voronoi图

4.2 线段加权Voronoi图的离散生成

4.2.1 线段加权Voronoi图的离散生成法的基本思想

4.2.2 线段加权Voronoi图离散生成算法及图例

4.3 实现算法的几个关键技术

4.3.1 两条线段是否相交的判断

4.3.2 母点的设置原则

4.3.3 Voronoi区域涂满的判定

4.3.4 关于Voronoi边的近似抽出

4.4 作图实例(用VC++6.0语言实现)

4.5 与已有算法的比较和分析

第五章 应用实例

5.1 绿化问题

5.2 水域划分问题

第六章 总结与展望

6.1 本文工作总结

6.2 进一步研究工作

参考文献

致谢

附录