voronoi diogram的相關知識

In mathematics, a Voronoi diagram, named after Georgy Voronoi, also called a Voronoi tessellation, a Voronoi decomposition, or a Dirichlet tessellation (after Lejeune Dirichlet), is a special kind of decomposition of a metric space determined by distances to a specified discrete set of objects in the space, e.g., by a discrete set of points.

In the simplest case, we are given a set of points S in the plane, which are the Voronoi sites. Each site s has a Voronoi cell, also called a Dirichlet cell, V(s) consisting of all points closer to s than to any other site. The segments of the Voronoi diagram are all the points in the plane that are equidistant to two sites. The Voronoi nodes are the points equidistant to three (or more) sites.

For any (topologically) discrete set S of points in Euclidean space and for almost any point x, there is one point of S closest to x. The word "almost" is used to indicate exceptions where a point x may be equally close to two or more points of S.

If S contains only two points, a and b, then the set of all points equidistant from a and b is a hyperplane—an affine subspace of codimension 1. That hyperplane is the boundary between the set of all points closer to a than to b, and the set of all points closer to b than to a. It is the perpendicular bisector of the line segment from a and b.

In general, the set of all points closer to a point c of S than to any other point of S is the interior of a (in some cases unbounded) convex polytope called the Dirichlet domain or Voronoi cell for c. The set of such polytopes tessellates the whole space, and is the Voronoi tessellation corresponding to the set S. If the dimension of the space is only 2, then it is easy to draw pictures of Voronoi tessellations, and in that case they are sometimes called Voronoi diagrams.

Voronoi圖是1907俄國數學家Voronoi提出的。它是對平面的一個劃分，每個分區表示一些點的軌跡，這些點到點集中的某個點比到其它點更近；它構成並表達但不相連的平面離散點群實體之間的空間鄰近拓撲關係。

定義

從Voronoi diogram是對平面n個離散數而言，它把平面分為幾個區，每一個區包括一個點，該點所在的區域是該點最近距離點的集合

1. 設平面A是一個已確定了尺度的量度平面。

2. 設P是一離散點集合P1，P2，…PnÎP，定義Pi的Voronoi區域V（Pi）為所有到Pi距離最小點的集合：V（Pi）={P/d（P， Pi）≤d（P，Pj），j≠i，j=1，2，…n}

3. 假設P是一離散點集合，P1，P2，…PnÎP定義P的Voronoi diogram V（P）為V（P）={V（P1），V（P2），…，V（Pn ）}其中Pi稱為V圖生成元。

地理空間（2維）對Voronoi diogram的擴展定義

一、Voronoi diogram定義
1. 2維地理空間G是由n個點、線、面實體集合g1，g2，……gn組成的，則該地理空間是定義了一種尺度d的量度空間。
2. 設G是由n個實體組成的集合，g1，g2，…，gnÎG，定義gi的Voronoi區域V（gi）為所有到gi距離最小點（柵格）的集合V(gi )={p/d(p,gi)≤d(p,gj), i≠j, j=1, 2, …，n}
3. 設G是由n個實體組成的集合，g1，g2，…gnÎG，定義G的Voronoi圖V（G）為 V（G）={V（g1），V（g2），…，V（gn）}
顯然，2維地理空間同樣有類似9-3的性質。必須明確，Voronoi diogram是與距離緊密相關的，而距離值是由尺度所基本定義的。不同尺度，距離的概念不一樣，數值往往也不一樣，因此不同的尺度空間，有不同的V圖。上述定義同樣可推廣到3維。

二、廣義Voronoi diogram
拓展Voronoi diogram為廣義Voronoi diogram具有廣泛意義。
1. 設G是由n個實體組成的集合，g1，g2，…，gnÎG，且各實體具有權ki,定義gi的Voronoi區域V（gi）為所有到gi加權距離最小點（柵格）的集合 V(gi)={p│kid(p,gi)≤kj d(p,gj), i≠j, j=1, 2, …，n}
2. 設G是由n個實體組成的集合，g1，g2，…gnÎG，定義G的Voronoi圖V（G）為V（G）={V（g1），V（g2），…，V（gn）}
一般V圖特性在廣義V圖中類似存在。

V圖生成方法
矢量方法生成Voronoi簡述

一、對偶生成法

所謂對偶生成法主要是指生成Voronoi diogram時先生成其對偶元Delaunay三角網，再通過做三角網每一三角形三條邊的中垂線，形成以每一三角形頂點為中間點的多邊形網，如圖1，是用對偶生成法生成的Voronoi diogram。

二、增添法
增添法生成V圖的基本概念是：假設平面上原有n個點（生成元），已生成了Vn圖，現在增加一個生成元Pn+1，這時生成新 的Vn+1圖。由於Voronoi diogram的特性，加入一個新生成元只與新元所在Voronoi多邊形及與i相鄰其它Voronoi多邊形“迎向半邊”有關，與這些多邊形的 “另半邊”無關，也與除它們之外的其它生成元的Voronoi多邊形無關。

三、部件合成法
部件合成法是指把生成元點集分為若干個子集，並且這些子集的並集必須為生成 元點集，為避免不必要麻煩，這些子集相互的交集盡可能小或為空集φ 。先對這些子集生成子V圖，然後把這些子V圖合併，修正其相互影響部分的Voronoi多邊形，從而得到全生成元點集的V圖。

栅格生成Voronoi diogram方法

一、數學形態學距離變換法
這方法主要如前第七章距離變換中所述
二、地圖代數的Voronoi diogram生成
地圖代數Voronoi diogram生成方法可以處理一定尺度空間下全部點、線、面實體，此方法理論上嚴密，算法簡潔、高效、精密，並已成為實用化的技術。這種方法可以很方便地推廣到三維及多維。
三、有障礙空間的V圖生成
對於有障礙物的地理空間，採用顧及了障礙的歐氏距離變換，其餘方法和步驟均同。
四、Bimedial圖生成

Voronoi diogram意義和應用

Voronoi diogram意義
1. Voronoi diogram特性
voronoi多邊形圖由點集生成擴展為由點、線、面集生成後，Voronoi diogram特性就變為以下三個：
（1）每個V多邊形內有一個生成元；
（2）每個V多邊形內點到該生成元距離短於到其它生成元距離；
（3）多邊形邊界上的點到生成此邊界的生成元距離相等；
（4）鄰接圖形的Voronoi多邊形界線以原鄰接界線作為子集。
2. Voronoi diogram是空間鄰近關係客觀、全面、準確的體現V圖給出了鄰近的準確量度。鄰近決定於空間尺度,是一種幾何關係,而”鄰”是一種拓撲關係,兩者不一樣。複雜的連續函數內插要在鄰近點間進行，Voronoi diogram給出了主影響元、鄰近影響元，提供了優良內插方法的優秀環境。
3. Voronoi diogram、障礙Voronoi diogram、廣義Voronoi diogram的多邊形邊界提供了點、線、面全形態，障礙、非障礙完備空間，廣義加權距離的等距線、等比線、等勢線等具有嚴密數學 意義且極廣泛使用價值的軌跡線:例如,它在等高線中就是半距、1/4距或n/m (n,<=m)距等高線,在交會線中便是角平分線或彎曲對稱軸,在封閉圖形中便是中軸線或Bimedial骨架，而封閉等高線組中便是分水線和匯水 線等地形結構線，…它實際上描繪了大自然幾何或者說地圖圖形幾何的輪廓。

Voronoi diogram的應用
一、最近鄰近查詢
二、障礙空間上優良內插方法
三、廣義對稱軸線的解算
四、空間結構

學習要點
1. 從Voronoi結構所脫胎的計算幾何來看，V圖是對平面n個離散點而言的，它把平面分為幾個區，每一個區包括一個點，該點所在的區是到該點距離最近 點的集合。 V圖是與距離緊密相關的，而距離值是由尺度所基本定義的。不同尺度，距離的概念不一樣，數值往往也不一樣，因此不同的尺度空間，有不同的Voronoi diogram。

2. 掌握矢量和柵格情況下的各種V圖生成方法。理解什麼是Bimedial圖，並了解其生成方法。

3. 理解V圖的特性，了解各種V圖的應用。

Resource: wuhan university_school of resource &environment science