Voronoi图由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“voronoi图”。
Voronoi图定义
任意两点p 和q 之间的欧氏距离，记作 dist(p, q)。就平面情况而言，我们有
dist(p, q)=(px-qx)2+(py-qy)
2设P := {p1, „, pn}为平面上任意 n 个互异的点；这些点也就是基点。按照我们的定义，所谓P对应的Voronoi图，就是平面的一个子区域划分——整个平面因此被划分为n 个单元（cell），它们具有这样的性质：
任一点q位于点pi 所对应的单元中，当且仅当对于任何的pj∈Pj, j≠i,都有dist(q, pi)
任给平面上两点p 和q，所谓 p 和q 的平分线（bisector），就是线段 pq的垂直平分线。该平分线将平面划分为两张半平面（half-plane）。点 p 所在的那张开半平面记作 h(p, q)，点 q 所在的那张开半平面记作 h(q, p)。请注意，r ∈ h(p, q)当且仅当 dist(r, p)
V(pi)= ∩ h(pi, pj), 1≤j≤n, j≠ i
也就是说，V(pi)是(n-1)张半平面的公共交集；它也是一个（不见得有界的）开的凸多边形（convex polygon）子区域.很显然，Voronoi顶点到相邻的三个site距离相等；Voronoi边上任意一点到相邻的两个site距离相等；
对于任何点q，我们将以q为中心、内部不含P中任何基点的最大圆，称作q关于P的最大空圆（largest empty circle），记作Cp(q)。以下定理指出了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算法，它主要由两部分组成：sweep line（扫描线）和beach line（海滩线）；
Fortune算法建立在点、线之间的距离关系上，如下图所示，平面上任意一点到一个点p的距离与到一条直线l的距离相等，这样的点有很多，它们构成的轨迹就是抛物线，点p就是抛物线的焦点，直线l就是抛物线的准线；
2、回到Fortune算法，这个固定点p就是一个site，l就是sweep line； sweep line自上而下扫描，平面区域任何点到site与sweep line距离相等的点构成一条抛物线（site就是抛物线的焦点），则n个site的抛物线相交的若干段抛物线弧构成beach line，如下图的蓝色抛物线弧集合；
抛物线之间的交点称为断点（break point），每个断点都落在某条Voronoi 边上。这并非巧合，随着扫描线自上而下扫过整个平面，所有断点的轨迹合起来恰好就是待构造的Voronoi图；（几何证明：断点到相邻的两个site距离总是相等，这个关系随着sweep line的扫描一直不变，则断点的运动轨迹就是这两个site的垂直平分线，也即Voronoi 边，两条Voronoi 边相交又产生Voronoi 顶点）
beach line上方的Voronoi 顶点和Voronoi 边已确定，将不会再变化。beach line（曲线）和它上方的直线构成当前的Voronoi 边，最后随着sweep line的移动而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的抛物线将逐渐伸展开来。
site event发生后引起的变化：因为沿海滩线上各个断点的运动轨迹，就勾勒出了Voronoi 图的各边。所以每发生一次site事件，就会生成两个新的断点，此后它们会逐渐地勾勒出同一条新边。
那为什么是同一条新边呢？实际上，在刚刚诞生的那一瞬间，这两个断点相互重合，然后才会各自朝相反的方向运动，而且它们所勾勒的都是同一条边（同break point定义处的几何证明）。在一开始，这条边与Voronoi图位于扫描线之上的其它部分并不相联。随着这条边的不断生长，直到后来它们与其它边相遇，此时它才会与Voronoi图的其它部分联接起来。
定理：只有在发生某个site事件时，海滩线上才会有新的弧出现。
2）、circle event
发生于原有的某段弧收缩为一点并即将消失时，假设三段连续的弧α、α '和α ''，这三段弧必然分别对应于三个不同基点pi、pj和pk，就在α'即将消失的那一刻，这三个基点所对应的抛物线将相交于同一点q。此时点q 到扫描线l 与到这三个基点等距离。亦即，存在一个以q 为中心、穿过pi、pj和pk 的圆，且该圆在最低点处与l 相切。该圆的内部不可能有任何基点——否则，q 到该基点将比到l 更近，而这却与“q 位于海滩线上”的事实不合。因此，点q 必是Voronoi图的一个顶点。
若海滩线上有某段弧消失，并因而有两段弧汇合起来，则相应地在Voronoi图中肯定也会有两条边汇合起来（成为一条新的边）。海滩线上依次首尾相联的任何三段弧，其对应的三个基点都会确定一个外接圆；当扫描线触及某个这类外接圆的最低点时，也就发生了一次圆事件（circle event）
定理：海滩线上已有的弧，只有在经过某次圆事件之后，才有可能消失。
简单点说，site event发生时，beach line会产生一条新弧，同时就会有一条新边出现并朝两端生长，慢慢形成新的Voronoi边；circle event发生时，会有两条正在生长的Voronoi边汇合起来，并在接合处形成一个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，外接圆y坐标最小的点（图中最低的小红点）将进入PQ，但是在sweep line碰到它之前，先扫描到了site p7，这样一来将产生新弧，破坏了原来的
三元组。发生circle event时，并不知道这是一个false alarm，所以直到碰到该外接圆内部存在site。这时需要把这个circle event去掉，也即删除原先进入PQ中的最低点。也说明了这个外接圆的圆心不是Voronoi顶点，属于误报。
2）、circle event：该事件还没有来得及真正发生，这一邻接弧三元组就已经消失了。
如下面三个图例，
三元组先产生外接圆，第一个小红点进入PQ，当sweep line扫描到p1时，
三元组也产生外接圆，第二个小红点进入PQ；但是，当sweep line扫描到第一个小红点时，它从PQ出队，随着sweep line下移，α3消失，合并为破坏了原来的三元组，则
无法形成Voronoi顶点，也即这个circle event属于误报。需要删除PQ中第二个小红点。
图像说明： bayanbox.ir/id/33679***743?download
http://www.daodoc.com/
