网络Voronoi图生成

论文总字数：29557字

摘 要

本文将自行设计一种网络Voronoi图生成算法并进行实验测试，最终对算法进行评估。Voronoi图是GIS空间分析中十分重要的工具，是基于距离/邻近性分析的基本方法之一。普通的基于欧氏距离的Voronoi图在范围较小且路网密度较大的地方会出现不可忽视的偏差。除此之外，网络Voronoi图还有简单解决有向问题，易于解决三维空间问题等相对于基于平面空间分析的普通Voronoi图的优势。并且由于目前相关工具非常匮乏，所以本文主要关注网络Voronoi图的生成。最后会使用Visual Studio 2013中的Python Profiling组件对算法进行分析和评估。

关键词：网络Voronoi图；Voronoi图；网络空间数据库

DESIGN AND TEST OF A KIND OF ALGORITHM FOR

NETWORK VORONOI DIAGRAM

Abstract:We will design a kind of Voronoi algorithm and test, then make an assessment of algorithm. Voronoi diagrams are very important tools in GIS spatial analysis which is based on the distance/proximity and one of the basic methods of analysis. Ordinary Voronoi diagram based on the Euclidean distance will result noticeable deviations in small area and complex road network. In addition, compare to General Voronoi Diagram based on planar spatial analysis, Network Voronoi Diagrams also have other advantages like more straightforward to solve the network problem, easy to solve the problem of three-dimensional space and so on. Then because of the current lack of tools, this article will focus on formation of Network Voronoi Diagram. At last I’ll use Python Profiling component in Visual Studio 2013 on algorithm analysis and assessment.

KEY WORDS：Network Voronoi Diagram; Voronoi Diagram; Network Spatial Database

目 录

摘要 ··········································································································· I

Abstract ······································································································ II

1. 绪论 ······························································································· 1
   1. 引言 ························································································· 1
   2. 网络Voronoi图研究现状 ······························································· 1
   3. 网络Voronoi图生成常用方法 ························································· 2

1.3.1 基于水流扩展思想的网络空间Voronoi图生成算法 ······················· 2

1.3.2 基于局部聚类思想的网络Voronoi图的生成算法 ·························· 2

1.4 网络Voronoi图的应用 ·································································· 3

1.4.1 大规模多仓库物流配送路径优化 ·············································· 3

1.4.2 城镇影响区域的划分 ····························································· 3

1.4.3 动物交通事故 ······································································ 3

1.4.4 街头犯罪的制止 ··································································· 3

1.4.5 海洋/海岸生物的行为调查 ······················································ 4

1.4.6 神经生物学中对脑区划分的帮助 ·············································· 4

第二章 网络Voronoi图的理论基础 ···································································5

2.1 平面Voronoi图 ············································································ 5

2.1.1 平面Voronoi的基本概念 ······················································· 5

2.1.2 平面Voronoi的生成方法 ······················································· 5

2.2 网络空间数据库 ··········································································· 6

2.2.1 网络空间事件：网格上事件和网格边事件 ································· 6

2.2.2 平面空间分析及其局限性 ······················································ 6

2.2.3 网络空间分析及其重要特征 ··················································· 7

2.3 网络Voronoi图的原理 ··································································· 8

2.3.1 平面与网络Voronoi图 ·························································· 8

2.3.2 朴素网络Voronoi图的几何性质 ·············································· 8

2.4 网络Voronoi图相对于传统Voronoi图的优势和劣势 ····························· 9

第三章 网络Voronoi图的算法设计 ································································ 10

3.1 多元最短路径算法（Multisource Dijkstra method） ································· 10

3.2 朴素网络Voronoi图的生成算法 ······················································ 11

3.3 有向Voronoi图的生成算法 ·························································· 11

3.4其他重要函数 ·············································································· 12

第四章 生成算法程序的测试与评估 ······························································· 12

4.1 算法执行情况 ············································································· 12

4.2 算法评估 ··················································································· 13

结论 ·········································································································· 15

参考文献（References） ·················································································· 17

致谢 ·········································································································· 18

剩余内容已隐藏，请支付后下载全文，论文总字数：29557字