第七章
Voronoi图构建算法
（based on Vector）
2011.6
GIS原理与算法
Voronoi图
Voronoi图是计算几何中最重要的几何结构之一（紧次于凸壳），
它描述了对于一系实体集的邻近性问题。
邮局问题；
观测台问题；
学校（医院）问题；
Voronoi图
Voronoi图的概念是由Dirichlet在1850年首先提出； 俄国数学家Voronoi于1907年在文章中做了进一步阐述，并提出高次方程化简；
气象学家Thiessen在1911年为了提高大面积气象预报结果，应用Voronoi图对观测站进行划分观测区域（多边形）；
为了纪念这些科学家的成就，这种结构被称为Dirichlet剖分或Voronoi图或Thiessen多边形。
主要内容
Definitions & Properties (定义和性质) Vector Algorithm (矢量算法)
Order-k VD (多阶VD)
Line and area VD (线和面的VD)
Minkowski metric VD (M度量VD)
Other Voronoi diagram (其他VD)
Applications (应用)
}i
Properties（1）
假设：集合S中，没有四点是共圆的。
Voronoi图是度数为三的正则图（图论），即：Voronoi图的每一个顶点恰好是图解的三条边的交点。
在S中，pi的每一个最邻近点确定一条Voronoi图多边形的一条边。
多边形V（i）是无界的当且仅当pi是集合S的凸壳的边界上的一个点。
对于S的Voronoi图的每一个顶点v，圆C（v）不包含S 的其它的点（最大空圆）。
Properties of D(p)& V(p)
Each Voronoi region
2、Vector Algorithm
•自Shamos和Hoey[1975]把Voronoi图作为一种有效的数据结构引入计算机领域，并成为计算几何领域的主要研究热点之一。
•许多学者对：
•平面点集Voronoi图的算法[Shamos & Hoey, 1975;
Hwang,1979; Lee,1980,………]
•平面特殊复杂实体的Voronoi算法，如线段
[Kirkpatrick, 1979]、线状或非交圆片状[Lee, 1981]、任意圆片状[Sharir,1985]、平面凸壳[Leven &
Sharir,1987]和曲线[Yap,1987] 等做了深入的研究，
并建立了许多有效的算法，
以上算法都是以离散点集算法为基础。
经典点
2.1 增量法(Incremental Method)
1.基本原理：
增量法
2. 边界问题
三点设置：
增量法
增量法
4.数据的层次组织
增量法
增量法
5.详细算法
增量法
2.2 分治法(Divide-and-conquer Method)
1.基本原理：
分治法
1.基本原理：
分治法
2.Assumptions & preprocess
•点按X坐标的增量排序，表示为：
•三个假设：
•Numerical computation is carry out in precise arithmetic;
•No four generators align on a common circle;
•No two generators align vertically.
分治法
3. 算法结构：
3.4
3.1
3.1
3.1
分治法
分治法
3.2
分治法
分治法
3.4
分治法
扫描法——预处理
扫描法——预处理
扫描法——算法
SDGF
扫描法
SDGF
扫描法
Complexity analysis:
扫描法-2
SDGF
SDGF
扫描法-2
扫描法-2
Sites event:
扫描法-2
Vertex events
扫描法-2
扫描法-2
Data structure:
At a site event a new edge starts to grow;
At a circle event two growing edges meet to form a vertex.
Two standard data structure :
An event queue;
A structure that represents the status of the sweep line;
1) Bounding box:
扫描法-2
2) The beach line is represented by a balanced binary search tree :
Its leaves correspond to the arcs;
It is x-monotone -----in an ordered manner;
Each leaf store the site that defines the arc it represents;
A breakpoint is stored at an internal node by an order tuple
of sites <pi, pj>;
扫描法-2
3) Detecting the circle events:
Two breakpoints in the consecutive triples not converge;
Even if a triple has converging breakpoints, the corresponding circle event need not take place----a false alarm;
The triple with the new arc being the middle one can never
cause a circle event;
扫描法-2。