障碍Voronoi图的结晶生成

摘要

该文用结晶生成方法来生成障碍Voronoi图.该方法的基本思想框架是:以生成元为生长点进行4-模板或8-模板的结晶生长,遇到障碍则将障碍边界加入生成元点集继续选择这两个模板结晶,最后得到不同结晶区域的交线图即为障碍Voronoi图.该方法可得到城区距离、棋盘距离和欧氏距离下的三种Voronoi图;该方法适用于障碍为任意平面区域的二维障碍Voronoi图的生成,而且所用数据结构简单,并已用VC++编程实现.文末,给出实例.应用此算法对某地区进行区域划分,解决学生就近入学问题.

目录

文摘

英文文摘

第一章绪论

1.1 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.3障碍Voronoi图已有的生成方法

第四章障碍Voronoi图的结晶生成

4.1预备知识

4.2结晶生长的定义

4.3结晶生成Voronoi图的定义

4.4障碍Voronoi图的结晶生成法

4.4.1结晶生成法介绍

4.4.2障碍Voronoi图的结晶生成法基本思想

4.4.3算法及图例

4.4.4关于一些具体算法的解释

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

第五章应用实例

5.1购物问题

5.2入学问题

第六章结束语

参考文献

致谢

附录