一、問題描述

1.Voronoi圖的定義

又叫泰森多邊形或Dirichlet圖，它是由一組由連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形組成。

2.Voronoi圖的特點(diǎn)

（1）每個(gè)V多邊形內(nèi)有一個(gè)生成元；
（2）每個(gè)V多邊形內(nèi)點(diǎn)到該生成元距離短于到其它生成元距離；
（3）多邊形邊界上的點(diǎn)到生成此邊界的生成元距離相等；
（4）鄰接圖形的Voronoi多邊形界線以原鄰接界線作為子集。

3.Voronoi的應(yīng)用

在計(jì)算幾何學(xué)科中的重要地位，由于其根據(jù)點(diǎn)集劃分的區(qū)域到點(diǎn)的距離最近的特點(diǎn)，其在地理學(xué)、氣象學(xué)、結(jié)晶學(xué)、航天、核物理學(xué)、機(jī)器人等領(lǐng)域具有廣泛的應(yīng)用。如在障礙物點(diǎn)集中，規(guī)避障礙尋找最佳路徑。

二、算法分析與設(shè)計(jì)

Voronoi圖有著按距離劃分鄰近區(qū)域的普遍特性，應(yīng)用范圍廣。生成V圖的方法很多，常見的有分治法、掃描線算法和Delaunay三角剖分算法。

1.建立Voronoi圖方法和步驟

本次實(shí)驗(yàn)采用的是Delaunay三角剖分算法。主要是指生成Voronoi圖時(shí)先生成其對(duì)偶元Delaunay三角網(wǎng)，再找出三角網(wǎng)每一三角形的外接圓圓心，最后連接相鄰三角形的外接圓圓心，形成以每一三角形頂點(diǎn)為生成元的多邊形網(wǎng)。如下圖所示。

建立Voronoi圖算法的關(guān)鍵是對(duì)離散數(shù)據(jù)點(diǎn)合理地連成三角網(wǎng)，即構(gòu)建Delaunay三角網(wǎng)。
建立Voronoi圖的步驟為：
（1）離散點(diǎn)自動(dòng)構(gòu)建三角網(wǎng)，即構(gòu)建Delaunay三角網(wǎng)。對(duì)離散點(diǎn)和形成的三角形編號(hào)，記錄每個(gè)三角形是由哪三個(gè)離散點(diǎn)構(gòu)成的。
（2）計(jì)算每個(gè)三角形的外接圓圓心，并記錄之。
（3）遍歷三角形鏈表，尋找與當(dāng)前三角形pTri三邊共邊的相鄰三角形TriA，TriB和TriC。
（4）如果找到，則把尋找到的三角形的外心與pTri的外心連接，存入維諾邊鏈表中。如果找不到，則求出最外邊的中垂線射線存入維諾邊鏈表中。
（5）遍歷結(jié)束，所有維諾邊被找到，根據(jù)邊畫出維諾圖。

2. Delaunay三角網(wǎng)的生成

建立Voronoi圖的關(guān)鍵是Delaunay三角網(wǎng)的生成。Delaunay三角網(wǎng)的特性：
（1）空?qǐng)A性，任一三角形外接圓內(nèi)部不包含其他點(diǎn)。
（2）最接近：以最近臨的三點(diǎn)形成三角形，且各線段(三角形的邊)皆不相交。
（3）唯一性：不論從區(qū)域何處開始構(gòu)建，最終都將得到一致的結(jié)果。
（4）最優(yōu)性：任意兩個(gè)相鄰三角形形成的凸四邊形的對(duì)角線如果可以互換的話，那么兩個(gè)三角形六個(gè)內(nèi)角中最小的角度不會(huì)變大。
（5）最規(guī)則：如果將三角網(wǎng)中的每個(gè)三角形的最小角進(jìn)行升序排列，則Delaunay三角網(wǎng)的排列得到的數(shù)值最大。
（6）區(qū)域性：新增、刪除、移動(dòng)某一個(gè)頂點(diǎn)時(shí)只會(huì)影響臨近的三角形。
（7）具有凸多邊形的外殼：三角網(wǎng)最外層的邊界形成一個(gè)凸多邊形的外殼。
Delaunay剖分是一種三角剖分的標(biāo)準(zhǔn)，實(shí)現(xiàn)它有多種算法。本次采用Bowyer-Watson算法，算法的基本步驟是：
（1）構(gòu)造一個(gè)超級(jí)三角形，包含所有散點(diǎn)，放入三角形鏈表。
（2）將點(diǎn)集中的散點(diǎn)依次插入，在三角形鏈表中找出其外接圓包含
插入點(diǎn)的三角形（稱為該點(diǎn)的影響三角形），刪除影響三角形的公共邊，將插入點(diǎn)同影響三角形的全部頂點(diǎn)連接起來，從而完成一個(gè)點(diǎn)在Delaunay三角形鏈表中的插入。
（3）根據(jù)優(yōu)化準(zhǔn)則對(duì)局部新形成的三角形進(jìn)行優(yōu)化。將形成的三角形放入Delaunay三角形鏈表。
（4）循環(huán)執(zhí)行上述第2步，直到所有散點(diǎn)插入完畢。

關(guān)鍵步驟2如下圖所示：

步驟3的局部?jī)?yōu)化的準(zhǔn)則指的是：
1.對(duì)新形成的三角形進(jìn)行優(yōu)化，將兩個(gè)具有共同邊的三角形合成一個(gè)多邊形。
2.以最大空?qǐng)A準(zhǔn)則作檢查，看其第四個(gè)頂點(diǎn)是否在三角形的外接圓之內(nèi)。
3.如果在，修正對(duì)角線即將對(duì)角線對(duì)調(diào)，即完成局部?jī)?yōu)化過程的處理。

LOP (Local Optimization Procedure)處理過程如下圖所示：

3.數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

本程序的實(shí)現(xiàn)采用C#面向?qū)ο笳Z言實(shí)現(xiàn)，故數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)采用類的形式，具體有：

點(diǎn)：
    public class Site
    {
        public double x, y;
        public Site()
        { }
        public Site(double x, double y)
        {
            this.x = x;
            this.y = y;
        }
    }
邊：
    public class Edge
    {
        public Site a, b;
        public Edge(Site a, Site b)
        {
            this.a = a;
            this.b = b;
        }
    }
三角形：
    public class DelaunayTriangle
    {
        Voronoi voronoi = new Voronoi();
        public Site site1, site2, site3;//三角形三點(diǎn)
        public Site centerPoint;//外界圓圓心
        public double radius;//外接圓半徑
        public List<DelaunayTriangle> adjoinTriangle;//鄰接三角形 

        public DelaunayTriangle(Site site1,Site site2,Site site3)
        {
            centerPoint = new Site();
            this.site1 = site1;
            this.site2 = site2;
            this.site3 = site3;
            //構(gòu)造外接圓圓心以及半徑
            voronoi.circle_center(centerPoint, site1, site2,site3,ref radius);
        }
    }

4. 算法復(fù)雜度分析

時(shí)間復(fù)雜度：
Delaunay三角網(wǎng)的生成的時(shí)間復(fù)雜度：
步驟一：構(gòu)造一個(gè)超級(jí)三角形，O（1）；
步驟二：產(chǎn)找影響的三角形，構(gòu)造新的三角形，O（1+2+…+n）=O(n2)O（1+2+…+n）=O(n2)
步驟三：對(duì)新形成的三角形進(jìn)行優(yōu)化局部?jī)?yōu)化：O(n)。
因此，整體時(shí)間復(fù)雜度是：O(1)+O(n2)+O(n)=O(n2)O(1)+O(n2)+O(n)=O(n2)。

從Delaunay三角網(wǎng)生成Voronoi圖的時(shí)間復(fù)雜度：
步驟一：構(gòu)造構(gòu)建Delaunay三角網(wǎng)，O(n2)O(n2)；
步驟二：計(jì)算三角形外接圓圓心，O(n)；
步驟三：尋找三角形三邊相鄰三角形：3O(n)；
步驟四：找到的維諾邊存入鏈表中，畫出維諾圖：O(n)。
因此，整體時(shí)間復(fù)雜度是O(n2)+O(n)+3O(n)+O(n)=O(n2)O(n2)+O(n)+3O(n)+O(n)=O(n2)。

三、實(shí)驗(yàn)結(jié)果

隨機(jī)生成點(diǎn)：

生成Delaunay三角形網(wǎng)：

生成Voronoi圖：

生成Voronoi圖的可執(zhí)行程序和源碼工程文件見here。

下面附上相關(guān)函數(shù)申明（詳細(xì)代碼見源碼工程文件）。

//根據(jù)點(diǎn)集構(gòu)造Delaunay三角形網(wǎng)
public void setDelaunayTriangle(List<DelaunayTriangle> allTriangle, List<Site> sites);

//根據(jù)Delaunay三角形網(wǎng)構(gòu)造Voronoi圖的邊
public List<Edge> returnVoronoiEdgesFromDelaunayTriangles(List<DelaunayTriangle> allTriangle, List<Edge> voronoiRayEdgeList);

//根據(jù)三角形鏈表返回三角形所有的邊
public List<Edge> returnEdgesofTriangleList(List<DelaunayTriangle> allTriangle);

//對(duì)新形成的三角形進(jìn)行局部?jī)?yōu)化
public List<DelaunayTriangle> LOP(List<DelaunayTriangle> newTriList);

//判斷邊是否屬于三角形
public bool isEdgeOnTriangle(DelaunayTriangle triangel,Edge edge);

//判斷點(diǎn)是否屬于三角形
public bool isPointOnTriangle(DelaunayTriangle triangle, Site site);

//將點(diǎn)與受影響的三角形三點(diǎn)連接，形成新的三個(gè)三角形添加到三角形鏈中
public void addNewDelaunayTriangle(List<DelaunayTriangle> allTriangles,DelaunayTriangle influenedTri,Site point);

//找出受影響的三角形的公共邊
public List<Edge> findCommonEdges(List<DelaunayTriangle> influenedTriangles);

//找出兩個(gè)三角形的公共邊
public Edge findCommonEdge(DelaunayTriangle chgTri1, DelaunayTriangle chgTri2);

//判斷插入點(diǎn)是否在三角形邊上
public Site[] isOnEdges(DelaunayTriangle triangle,Site site);  

//判斷點(diǎn)是否在三角形外接圓的內(nèi)部
public bool isInCircle(DelaunayTriangle triangle, Site site) ;

//求三角形的外接圓心
public void circle_center(Site center, Site sites0, Site sites1, Site sites2, ref double radius) ;

//求兩點(diǎn)之間距離
public double distance2Point(Site p,Site p2);

PS：由于時(shí)間和水平有限，博文難免有不足甚至錯(cuò)誤之處，僅供參考，歡迎批評(píng)指正。

參考文獻(xiàn)

[1]Voronoi.百度百科