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)。