-
Voronoi
图定义
任意两点
p
和
q
之间的欧氏距离，记作
dist(p, q)
。就平面情况而言，我们
有
dist(p, q) = (px-qx)2+ (py-
qy)2
设
P := {p1,
?
,
pn}
为平面上任意
n
个互异的点
；这些点也就是基点。按照
我们的定义，
所谓
< br>P
对应的
Voronoi
图，<
/p>
就是平面的一个子区域划分——整个平
面因此被划分为
n
个单元（
cell
），它们具有这样的性质：
<
/p>
任一点
q
位于点
pi
所对应的单元中，当且仅当对于任何的
pj
∈
Pj, j
≠
i,
都有
dist(q, pi)
。我们将与
P
对应的
Vor
onoi
图记作
Vor(P)
。
“
Vor(P)
”或者“
Voronoi
图”所指示的仅仅只是组成该子区域划
分的边和顶
点。在
Vor(P)
中，与
基点
pi
相对应的单元记作
V
(pi)
——称作与
pi
相对应的
Voronoi
单元（
< br>Voronoi
cell
）。上图是
< br>Voronoi
图，下图的蓝色点围成的区域
（凸包）是
它对应的
Delaunay
三角剖分。
任给平面上两点
p
和
q
，所谓
p
和
q
的平分线（
bisector
），就是线段
pq
的垂直平分线。该平分线将平面划分为两张半平面（
half-
plane
）。点
p
所在
的那张开半平面记作
h(p,
q)
，点
q
所在的那张开半平面记作
h(q, p)
。请
注意，
r
∈
h(p, q)
当且仅当
dist(r, p) < dist(r, q)
。据此，可以得出
如下观察结论：
V (pi) =
∩
h(pi, pj) ,
1
≤
j
≤
n,
j
≠
i
也就是说，
V (pi)
是
(n-1)
张半平面的公共交集；它也是一个（不见得有界的）
开的凸多边形（
convex
polygon
）子区域
.
很显然，
Voronoi
顶点到相邻的三个
site
距离相等；
Voronoi
边上任意一点到相
邻的两个
site
距离相等；
对于任何点
q
，我们将以
< br>q
为中心、内部不含
P
中任何基
点的最大圆，称作
q
关
于
P
的最大空圆
（
large
st empty
circle
）
，
记作
Cp(q)
。
< br>以下定理指出了
Voronoi
图的顶点及边所具有的特
征：
对于任一点集
P
所对应的
Voronoi
图
Vor(P)
，下列命题成立：
1)
点
q
是
Vor(P)
的一个顶点，当且仅
当在其最大空圆
Cp(q)
的边界上，至少
有三个基点；
(Voronoi
顶点是三个
site
的外接圆的圆心
)
2)
pi
和
pj
之间的平分线确定了
Vor
(P)
的一条边，当且仅当在这条线上存在
一个点
q
，
Cp(q)
的边界经过
pi
和
pj
，但
不经过其它站点。
构造
Voronoi
图
构造
Voronoi
图有四种算法：定义法（
Intersect
of Halfplanes
）、增量
（
incremental
）算法、分治法、
plane
sweep
算法；
1
、
plane
sweep
（平面扫描）
算法又名
Fortune
算法，
它主要由两部分组成：
< br>sweep
line
（扫描线）和
beach
line
（海滩线）；
Fortun
e
算法建立在点、线之间的距离关系上，如下图所示，平面上任意一点到
一个点
p
的距离与到一条直线
l
的距离相等，
这样的点有很多，
它们
构成的轨迹
就是抛物线，点
p
就是抛物
线的焦点，直线
l
就是抛物线的准线；
2
、回到
Fortune
< br>算法，这个固定点
p
就是一个
s
ite
，
l
就是
sweep line
；
sweep line
自上而下扫描，平面区域任何点到
site
与
sweep line
距离相等的
点构成一条抛物线（
site
就是抛物线的焦点），则
n
个
< br>site
的抛物线相交的若
干段抛物线弧构成
beach line
，如下图的蓝色抛物线弧集合；
抛物线之间的交点称为断点（
break
point
），每个断点都落在某条
Voronoi
边
上。
这并非巧合，
随着扫描线自上而下扫过整个平面，
所有断点的轨迹合起来恰
好就是待构造的
Voronoi
图
；（
几何证明：断点到相邻的两个
site
距离总是相
等，这个关系随着
sweep line
的扫描一直
不变，则断点的运动轨迹就是这两个
site
的垂直平分线，<
/p>
也即
Voronoi
边，
两条
Voronoi
边相交又产生
Voronoi
顶
点）
beach
line
上方的
Voronoi
顶点和
Voronoi
边已确定，将不会再变化。
beach
line
（曲线）和它上方的直线构成当前的
Voronoi
边，最后随着
sweep
line<
/p>
的
移动而
beach
line
也在不断下移，变为最终的
Voronoi
边；
（海滩线沿
x
方
向单调——即，它与任一垂线相交而且仅相交于一点。）
beach
line
属性
1
、
随着
sweep
line
下降，
break
points
跟踪
Voronoi
边；
一个新的
break
point
（新弧形成或者两个
break
point
融合为一体）产生一条新的边；
2
、两个
break point
相遇产生
voronoi
顶点
3
、
为了确
定
Voronoi
边和
Voronoi
顶点，
我们需要维护
beach
line
这个结构，
但是随着
l
的运动它会持续不断地更新。那么，应该如何表示
beach
line
结构
呢？
所谓
beach line
的组
合结构发生变化，指的是其上出现了新的抛物线弧，或原
有的某段抛物线弧收缩成一个点
并进而消失。在这个算法中，产生新弧，称为
site
event
；旧弧消失，称为
circle
event
。
两类事件
site
event
和
circle
event
：
1
）、
site
event
sweep line
扫
到某个
site
，设为
p
，在此瞬间，站点
p
对应于一条宽度为零的
退化抛物线——亦即，
将该新站点
p
与扫描线
l
联接起来的垂直线段。
随着扫描
线继续下移，这个宽度为
0
< br>的抛物线将逐渐伸展开来。
site event
发生后引起的变化：因为沿海滩线上各个
断点的运动轨迹，就勾勒
出了
Voronoi
图的各边。所以每发生一次
site
事件，就会生成两
个新的断点，
此后它们会逐渐地勾勒出同一条新边。
那为什么是同一条新边呢？实际上，
在刚刚诞生的那一瞬间，
这两个断点相互重
合，
然后才会各自朝相反的方向
运动，
而且它们所勾勒的都是同一条边
（同
break
point
定义处的几何证明）。在一开始，
这条边与
Voronoi
图位于扫描线之上的
< br>其它部分并不相联。
随着这条边的不断生长，
直到后来它
们与其它边相遇，
此时
它才会与
Vor
onoi
图的其它部分联接起来。
定理：只有在发生某个
site
事件时
，海滩线上才会有新的弧出现。
2
）、
circle
event
发生于原有的某段弧收缩为一点并即将消失时，假
设三段连续的弧
α
、
α
'
和
α
''
，这三段弧必然分别对应于三个不同基点
pi
、
pj
和
pk
，就在
α
'
即
将消
失的那一刻，这三个基点所对应的抛物线将相交于同一点
q
。此时点
q
到扫描
线
l
与到这三个基点等距离。
亦即，
存在一个以
q
为中心、
穿过
pi
、
pj
和
pk
的
圆，
且该圆在最低点处与
l
相切。
该圆的内部不可能有任何基点——否则，
q
到
该基点将比到
l
< br>更近，
而这却与
“
q
位于海滩线上”
的事实不合。
因此，
点
q
必
是
Voronoi
图的一个顶点。
若海滩
线上有某段弧消失，
并因而有两段弧汇合起来，
则相应地在
Voronoi
图中
肯定也会有两条边汇合
起来
（成为一条新的边）
。
海滩线上依
次首尾相联的任何
三段弧，
其对应的三个基点都会确定一个外接
圆；
当扫描线触及某个这类外接圆
的最低点时，也就发生了一次
圆事件（
circle event
）
定理：海滩线上已有的弧，只有在
经过某次圆事件之后，才有可能消失。
简单点说，
site
event
发生时，
beach line
会产生一条新弧，同时就会有一条
新边出现并朝两端生长，慢慢形成新的
Voronoi
边；
circle event<
/p>
发生时，会
有两条正在生长的
Voron
oi
边汇合起来，并在接合处形成一个
Voronoi
顶点，
同时中间的旧弧消失。
4
、异常情况
a false alarm
：
We
may have stored a circle event in the event list,
but
it may be that it never
happens
There are two
reasons for false alarms: site events and other
circle
events
我们存储了
circle
event
，
但它可能永远不会发生，
真是一个美
丽的错误
...
在
site
event
和
circle
event
发生时，都会有可能误报情况。
1
）、
site
event
：
circle event
发生时产生的最大空心圆内部还有其他
site
。
如下面三个图例，
p2
、
p3
、
p4
组成的外接圆，确定了一个
circle event
，外接<
/p>
圆
y
坐标最小的点（图中最低的小红点）
将进入
PQ
，但是在
sweep
line
碰到它
之前，先扫描到了
site
p7
，这样一来将产生新弧，破坏了
原来的
三
元组。
发生
circle
event
时，并不知道这是一个
false alarm
，所以直到碰到
该外接圆内部存在
site
。这时需要把这个
circle
ev
ent
去掉，也即删除原先进
入
PQ<
/p>
中的最低点。也说明了这个外接圆的圆心不是
Voronoi
顶点，属于误报。
2
）、
circle event
：该事件还没有来得及真正发生，这一邻接弧三元组就已经
消失了。
如下面三个图例，
三元组先产生外接圆，第一个小红点进入
PQ
，当
sweep
line
扫描到
p1
时，
三元组也产生外接圆，第二个小红点进入
PQ
< br>；
但是，
当
sweep
line
扫描到第一个小红点时，
它从
PQ
出队，
随着
sw
eep
line
下移，
α
3
消失，
<
α
2,
α
3,
α
4>
合并为
<
α
2,
α
4>
破坏了原来
的三元组，则