本算法的思想是，利用均匀网格(本文采用的网格数目为最接近点数的4的倍数），把所有点分入网格中，这些格网中的点构成VORONOI图，采用联机增量算法。然后利用分治算法中的区域合并方法，把所有的小方格所构成的VORONOI图组合起来成为完整的VORONOI图。
伪代码如下:
#ifnotdef voronoi.h
#def voronoi.h
//这里有三个类：point,voronoi,grid。point类用坐标来描述点的位置，voronoi则是平面点所构成的VORONOI图形，而grid是把point分布入其中的那些格网。
class point{
struct position{
int x;
int y;
}
int gridnum;
int seq;
int totalnum;
int gridnum;
}
class voronoi{
struct graph{
CDC Polygon();
}
struct onlineincremeth{
}
}
class grid{
void
int num.range；
int serial；
int totalnum；
int pointnum；
int pointtotalnum；
int layer；
int morton.availabledigit；
int morton.lastdigit;
①使用均匀格网分割构成VORONOI图的算法。
Pref 建立最接近现有点数目，以四的倍数为格子数的均匀格网。以四叉树格式存储格网。
Post 输出点所构成的VORONOI图。
Return Null
1 open file //打开点坐标的存储文件
2 read point.position //读点坐标
3 find_nearestquadronum(poin.totalnum,grid.num);//找到最接近点子总数的4的幂，以此数目作为栅格总数
4 create_grid(grid.num)//创建格网
4 loop(point.seq not exceed poin.totalnum) //依据坐标划分点进入格网
1find point.position in grid.num.range
2 point.gridnum=grid.serial
4 endloop
5 loop(grid.serial not exceed grid.stotalnum) //把格网中的点合并成为VORONOI图
1 loop(grid.pointnum not exceed grid.pointtotalnum)//对所在格网内的点数进行判断
1 If grid.pointnum<=1//如果点数不大于1，跳出循环
2 Break
3 else
4 voronoi_onlineincremeth(point.gridnum = grid.serial)
5 voronoi.gridnum=grid.serial
4 end loop
6 end loop
7 conjoin_voronoi_quartreemeth(voronoi.grid)//采用四叉树网格合并算法
②Conjoin_voronoi_quartreemeth:
Pref 我们首先需要把所有的小格网采用四叉数存储（存储的格式采用四进制的Morton码）
Post 通过把小的格网不断的归并起来，最终构成完整的VORONOI图。
Return VORONOI图
1 grid.layer=getlog(4,grid.num)//求网格的MORTON码的长度
2 loop(grid.layer not less than 1)//利用MORTON码长度进行VORONOI图合并
1 grid.morton.availabledigit= getlog(4,grid.num)-grid.layer+1.//找到栅格的MORTON码的有效末位
2 loop(grid.morton.availabledigit not less than 1) //设置阀值使得栅格的可用MORTON码有效位数不少于1
1 grid.morton.lastdigit=0//栅格MORTON码的最后一位的起始搜索值为0
1 loop(grid.morton.lastdigit not exceed 3)//进行循环来查找位于同一大四叉树网格内的小网格
1 grid1.morton.lastdigit=get(grid1.morton.lastdigit++)
2 grid2.morton.lastdigit=grid1.morton.lastdigit
1 if TRUE= compare (grid1.morton.lastdigit,grid2.morton.lastdigit)
1 voronoi.graph=conjoin_voronoi(grid1,grid2) //采用分治法中的VORONOI合并算法
2 end if
2 End loop
3 End loop
3 End loop
下面我们来分析算法的时间复杂度:
在第一部分的算法中，找出最接近点总数的格网数并创建格网需要花费常数时间，把所有点分入各个格网需要O(n)时间。对于下面部分的时间复杂度不一。最差情况就是O(n2)。
在第二部分算法中，第一步的操作中耗费的时间为O(log4n),后面合并VORONOI图的操作时间复杂度为O[log4n×(log4n+n2)],所以时间复杂度为O[log4n(n2)]。
综上所述，本算法的时间复杂度为O[n+n2+log4n(n2)]=O[log4n(n2)]。
看起来本算法时间耗费好像比较长，其实不一定，经过仔细研究。本算法对于均匀分布的点子算法时间耗费甚至可以降到O(log43n)。以16个点为例，O(log4316)=8，低于16本身。所以此算法适于均匀分布格网点。
