voronoi算法

⑴ 点集的Delaunay三角剖分方法

3.2.1.1 基本理论

B.Delaunay于1934年提出了Delaunay三角网格的概念，它是Voronoi图(简称V图)的几何对偶图，具有严格的数学定义和完备的理论基础。

图3.1 Voronoi图(虚线)及对应的Delaunay三角剖分(实线)

3.2.1.1.1 Voronoi图

假设V={v₁，v₂，…，v_N}，N≥3是欧几里得平面上的一个点集，并且这些点不共线，四点不共圆。用d(v_i，v_j)表示点v_i与v_j间的欧几里得距离。

设x为平面上的点，则:

区域V_(i)={x∈E²d(x，v_i)≤d(x，v_j)，j=1，2，…，N，j≠i}称为Voronoi多边形，也称为该点的邻域。点集中所有点的Voronoi多边形组成Voronoi图，如图3.1所示。

平面上的Voronoi图可以看做是点集V中的每个点作为生长核，以相同的速率向外扩张，直到彼此相遇为止而在平面上形成的图形。除最外层的点形成开放的区域外，其余每个点都形成一个凸多边形。

3.2.1.1.2 Delaunay三角剖分

Delaunay三角形网格为V图的几何对偶图。在二维平面中，点集中若无四点共圆，则该点集V图中每个顶点恰好是3个边的公共顶点，并且是3个Voronoi多边形的公共顶点;上述3个Voronoi多边形所对应的点集中的点连成的三角形称为与该Voronoi顶点对应的Delaunay三角形，如图3.1所示。如果一个二维点集中有四点共圆的情况，此时，这些点对应的Voronoi多边形共用一个Voronoi顶点，这个公共的Voronoi顶点对应多于3个Voronoi多边形，也就是对应于点集中多于3个的点;这些点可以连成多于一个的三角形。此时，可以任意将上述几个点形成的凸包划分为若干三角形，这些三角形也称为和这个Voronoi顶点对应的Delaunay三角形。

所有与Voronoi顶点对应的Delaunay三角形就构成了Delaunay三角剖分。当无退化情况(四点共圆)出现时，点集的Delaunay三角剖分是唯一的。

3.2.1.1.3 Delaunay三角剖分的特性

Delaunay三角剖分具有两个重要特性:

(1)最小角最大化特性:即要求三角形的最小内角尽量最大，具体地说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，6个内角的最小角不再增大，并且使三角形尽量接近等边。

(2)空外接圆特性:即三角形的外接圆中不包含其他三角形的顶点(任意四点不能共圆)，该特性保证了最邻近的点构成三角形，使三角形的边长之和尽量最小。

3.2.1.2 常用算法

Delaunay三角剖分方法是目前最流行的通用的全自动网格生成方法之一。比较有效的Delaunay三角剖分算法有分治算法、逐点插入法和三角网生长法等(Tsai，1993)，其中逐点插入法由于其算法的简洁性且易于实现，因而获得广泛的应用。其主要思路是先构建一个包含点集或区域的初始网格，再依次向初始网格中插入点，最后形成Delaunay三角剖分。

采用逐点插入法建立Delaunay三角网的算法思想最初是由Lawson于1977年提出的(Lawson，1977)，Bowyer和Watson等先后对该算法进行了发展和完善(Bowyer，1981;Watson，1981)。目前涌现出的大量逐点插入法中，主要为以Lawson算法代表的对角线交换算法和以Bowyer-Watson算法代表的空外接圆法。

3.2.1.2.1 Lawson算法

Lawson算法的主要思想是将要插入的数据点逐一插入到一个已存在的Delaunay三角网内，然后再用局部优化算法(Local Optimization Procere，LOP)优化使其满足Delau-nay三角网的要求，其主要步骤如下:

图3.7 Bowyer-Watson算法剖分实例

⑵ voronoi图的生成方法

四叉树归并构成VORONOI图的算法
}
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;

⑶ 几种GIS空间插值方法

GIS空间插值方法如下：

1、IDW

IDW是一种常用而简便的空间插值方法，它以插值点与样本点间的距离为权重进行加权平均，离插值点越近的样本点赋予的权重越大。 设平面上分布一系列离散点，已知其坐标和值为Xi，Yi, Zi （i =1，2，…，n）通过距离加权值求z点值。

IDW通过对邻近区域的每个采样点值平均运算获得内插单元。这一方法要求离散点均匀分布，并且密度程度足以满足在分析中反映局部表面变化。

2、克里金插值

克里金法（Kriging）是依据协方差函数对随机过程/随机场进行空间建模和预测（插值）的回归算法。

在特定的随机过程，例如固有平稳过程中，克里金法能够给出最优线性无偏估计（Best Linear Unbiased Prediction,BLUP），因此在地统计学中也被称为空间最优无偏估计器（spatial BLUP）。

对克里金法的研究可以追溯至二十世纪60年代，其算法原型被称为普通克里金（Ordinary Kriging, OK），常见的改进算法包括泛克里金（Universal Kriging, UK）、协同克里金（Co-Kriging, CK）和析取克里金（Disjunctive Kriging, DK）；克里金法能够与其它模型组成混合算法。

3、Natural Neighbour法

原理是构建voronoi多边形，也就是泰森多边形。首先将所有的空间点构建成voronoi多边形，然后将待求点也构建一个voronoi多边形，这样就与圆多边形有很多相交的地方，根据每一块的面积按比例设置权重，这样就能够求得待求点的值了。个人感觉这种空间插值方法没有实际的意义来支持。

4、样条函数插值spline

在数学学科数值分析中，样条是一种特殊的函数，由多项式分段定义。样条的英语单词spline来源于可变形的样条工具，那是一种在造船和工程制图时用来画出光滑形状的工具。在中国大陆，早期曾经被称做“齿函数”。后来因为工程学术语中“放样”一词而得名。

在插值问题中，样条插值通常比多项式插值好用。用低阶的样条插值能产生和高阶的多项式插值类似的效果，并且可以避免被称为龙格现象的数值不稳定的出现。并且低阶的样条插值还具有“保凸”的重要性质。

5、Topo to Raster

这种方法是用于各种矢量数据的，特别是可以处理等高线数据。

6、Trend

根据已知x序列的值和y序列的值，构造线性回归直线方程，然后根据构造好的直线方程，计算x值序列对应的y值序列。TREND函数和FORECAST函数计算的结果一样，但是计算过程完全不同。

⑷ 已知n个点坐标，求覆盖所有点的最小面积圆用什么算法

最简单的算法是任取三个点做一个圆，验证其他n-3个点是否在该圆内，并取遍所有的三个点的组合，记录其中最小的圆。这个算法的复杂度是O(n^4)。
另一种较好散搭岩的算法是Shamos提出的算法,复杂度是O(nlogn)。
S1. 计算点集S的凸壳CH(S)；
S2. 计算CH(S)的直径，设为p[i]p[j]，以p[i]p[j]为直径枝乱做圆C，如果S中的点都在圆C内，则C就是所求的最小覆盖圆；否则转S3；
S3. 计算点集S的最远点意义下的Voronoi图即Vor(S)；
S4. 设v是Vor(S)中的一个Voronoi点，以v为圆心，v至S点集冲御中3个最远点的距离为半径做圆，该圆就是所求。
S1可以在O(nlogn)内完成，S2需要O(n)时间，S3需要O(nlogn)时间，S4的复杂度是O(n)，所以整个算法的复杂度是O(nlogn)。