基于逐點(diǎn)插入法生成Voronoi圖的算法研究及實(shí)現(xiàn)

張　艷，李　強(qiáng)

(中國礦業(yè)大學(xué)(北京) 地球科學(xué)與測繪工程學(xué)院，北京 100083)

?

基于逐點(diǎn)插入法生成Voronoi圖的算法研究及實(shí)現(xiàn)

張艷，李強(qiáng)

(中國礦業(yè)大學(xué)(北京) 地球科學(xué)與測繪工程學(xué)院，北京 100083)

基于逐點(diǎn)插入法生成Voronoi圖需要首先生成Voronoi對(duì)應(yīng)的Delaunay三角剖分，為滿足大量離散點(diǎn)數(shù)據(jù)快速構(gòu)建Voronoi圖的效率需求，研究利用Lawson算法在形成三角網(wǎng)過程中進(jìn)行LOP優(yōu)化，快速生成可靠的Delaunay三角網(wǎng)，并應(yīng)用Delaunay三角網(wǎng)與Voronoi圖互為對(duì)偶的關(guān)系，構(gòu)建所需的Voronoi圖。在對(duì)大量的隨機(jī)離散數(shù)據(jù)進(jìn)行試驗(yàn)，并與標(biāo)準(zhǔn)的結(jié)果進(jìn)行對(duì)比后發(fā)現(xiàn)，除部分異常情況，利用該算法可以快速準(zhǔn)確地構(gòu)建出目標(biāo)Voronoi圖。

Delaunay三角剖分；LOP優(yōu)化；Voronoi圖；逐點(diǎn)插入法

Voronoi圖又稱泰森多邊形或者Dirichlet圖，它在求解點(diǎn)集或者其他幾何對(duì)象與距離有關(guān)的問題時(shí)有著重要的作用，應(yīng)用領(lǐng)域從幾何重構(gòu)到計(jì)算機(jī)圖形學(xué)、圖像處理，從路徑規(guī)劃到粒子微觀狀態(tài)分布，幾乎涵蓋了自然科學(xué)領(lǐng)域的大部分學(xué)科[1-4]，由于它的廣泛適用性，人們研究得出了一系列關(guān)于它的有效算法。

關(guān)于Voronoi的算法大致可以分為兩類[5-6]：一是直接法，即直接由點(diǎn)集生成Voronoi圖，比如半平面法、增量構(gòu)造法、分治法、平面掃描線法等；二是間接法，利用Voronoi 圖與 Delaunay 三角網(wǎng)互為對(duì)偶圖的關(guān)系，先對(duì)點(diǎn)集剖分生成 Delaunay 三角網(wǎng)，然后構(gòu)建Voronoi 圖。關(guān)于間接法的研究有任永功等人的利用類Delaunay三角網(wǎng)實(shí)現(xiàn)Voronoi圖[7]，劉少華等人的基于Delaunay三角網(wǎng)的泰森多邊形生成算法研究[8]，卓中文等用炮孔取樣點(diǎn)的數(shù)據(jù)作為數(shù)據(jù)源來研究基于Delaunay三角網(wǎng)生成Voronoi爆破圖[9]，孫繼忠等人針對(duì)Delaunay三角網(wǎng)生長算法和間接生成Voronoi圖算法構(gòu)網(wǎng)效率不高的問題，提出了一種基于Delaunay三角網(wǎng)間接生成Voronoi圖的改進(jìn)算法[10]。

逐點(diǎn)插入法是目前生成Delaunay 三角網(wǎng)應(yīng)用最廣泛的算法之一，該算法實(shí)現(xiàn)簡單，易于推廣到三維情況。本文基于逐點(diǎn)插入法進(jìn)行Delaunay 三角剖分，再由Delaunay 三角網(wǎng)的對(duì)偶圖成功地得到相關(guān)點(diǎn)集的Voronoi圖[11-14]。

1　構(gòu)建Voronoi步驟

算法實(shí)現(xiàn)的關(guān)鍵是對(duì)離散點(diǎn)進(jìn)行合理的剖分，使之連接形成Delaunay 三角網(wǎng)，基本步驟如下：

1)構(gòu)建Delaunay 三角網(wǎng)，對(duì)離散點(diǎn)和形成的三角形編號(hào)，記錄每個(gè)三角形是由哪3個(gè)離散點(diǎn)構(gòu)成的；

2)找出與每個(gè)離散點(diǎn)相鄰的所有三角形的編號(hào)，并記錄下來。只要在已構(gòu)建的三角網(wǎng)中找出具有一個(gè)相同頂點(diǎn)的所有三角形即可；

3)對(duì)與每個(gè)離散點(diǎn)相鄰的三角形按順時(shí)針或逆時(shí)針方向排序；

4)計(jì)算每個(gè)三角形的外接圓圓心，并記錄之；

5)根據(jù)每個(gè)離散點(diǎn)的相鄰三角形，連接這些相鄰三角形的外接圓圓心，得到Voronoi圖。

2　Delaunay 三角網(wǎng)的構(gòu)建

Delaunay 三角剖分對(duì)數(shù)值分析以及圖形學(xué)來說，是極為重要的一項(xiàng)預(yù)處理技術(shù)，它有最大化最小角，即“最接近于規(guī)則化的”三角網(wǎng)和唯一性，任意四點(diǎn)不能共圓兩個(gè)特點(diǎn)。

Delaunay剖分的生成算法主要有分治算法、逐步插入法、三角網(wǎng)生長法等。而逐點(diǎn)插入法的代表算法為1977年由Lawson提出的Lawson算法，該算法思路簡單，易于編程實(shí)現(xiàn)[15]。基本原理為：

1)構(gòu)造一個(gè)超級(jí)三角形，包含所有散點(diǎn)，放入三角形鏈表。

2)將點(diǎn)集中的散點(diǎn)依次插入，在三角形鏈表中找出外接圓包含插入點(diǎn)的三角形(稱為該點(diǎn)的影響三角形)，刪除影響三角形的公共邊，將插入點(diǎn)同影響三角形的全部頂點(diǎn)連接起來，完成一個(gè)點(diǎn)在Delaunay三角形鏈表中的插入，如圖1所示。

3)對(duì)局部新形成的三角形進(jìn)行LOP優(yōu)化，并將形成的三角形放入Delaunay三角形鏈表。

4)循環(huán)第二步，直到所有離散點(diǎn)插入完畢。

圖1　插入新點(diǎn)后過程

3　算法流程及實(shí)現(xiàn)

3.1Delaunay三角剖分的生成

Lawson三角剖分算法的關(guān)鍵是先創(chuàng)建包含點(diǎn)集的凸殼，在插入新點(diǎn)后快速生成新的三角網(wǎng)，并進(jìn)行LOP優(yōu)化，得到Delaunay三角網(wǎng)。采用面向?qū)ο蟮姆椒▽?shí)現(xiàn)程序的設(shè)計(jì)過程可以直觀明朗地獲取相關(guān)點(diǎn)、邊、三角形的信息。

3.1.1初始設(shè)置

1)點(diǎn)類和點(diǎn)列表：Class Point and class PointList；

2)邊類和邊列表：Class Edge and class EdgeList；

3)三角形類和三角形列表：class Triangle and class TriangleList。

3.1.2數(shù)據(jù)讀入

采用FileStream類，以文件流的形式讀入數(shù)據(jù)，數(shù)據(jù)采用X，Y坐標(biāo)形式，并利用GDI畫圖展點(diǎn)。

3.1.3建立凸殼

將數(shù)據(jù)存入點(diǎn)列表PointList，遍歷最大最小的X，Y坐標(biāo)值，用獲取的最大最小橫縱坐標(biāo)值定義超三角形SuperTriangle的3個(gè)頂點(diǎn)坐標(biāo)。

3.1.4生成Delaunay三角網(wǎng)

根據(jù)兩點(diǎn)構(gòu)成邊，三邊構(gòu)成三角形的原理，首先構(gòu)建點(diǎn)列表，由點(diǎn)列表得到邊列表，再由邊、點(diǎn)列表得到相應(yīng)的三角形鏈表，最終按照Lawson算法得到Delaunay三角網(wǎng)，效果如圖2所示。

圖2　75點(diǎn)生成的Delaunay三角網(wǎng)

3.2Voronoi圖的構(gòu)建

根據(jù)Voronoi圖與Delaunay三角網(wǎng)互為對(duì)偶圖的關(guān)系，在以生產(chǎn)Delaunay三角剖分的基礎(chǔ)上可以迅速地得到相應(yīng)的Voronoi圖。

3.2.1初始設(shè)置

1)Voronoi圖點(diǎn)列表：VPoint；

2)三角形邊列表：VEdgeList；

3)三角形列表：TriangleList；

4)邊另一點(diǎn)列表：OtherPointList。

3.2.2程序步驟

第一步：根據(jù)在Delaunay三角剖分過程中得到的三角形頂點(diǎn)列表，除去超級(jí)三角形頂點(diǎn)，然后依次將剩余點(diǎn)添加到新的VPoint列表。

第二步：遍歷三角形邊列表EdgeList，重新加入到VEdgeList邊列表，并同時(shí)去除重復(fù)的邊。

第三步：遍歷VPoint列表，對(duì)每一點(diǎn)遍歷該點(diǎn)相關(guān)的邊列表VEdgeList，在這一過程中，同時(shí)記錄邊列表相關(guān)的另一點(diǎn)及其坐標(biāo)值，并將該點(diǎn)即OtherPoint存入OtherPointList。

第四步：對(duì)OtherPointList內(nèi)的點(diǎn)按逆時(shí)針排序，計(jì)算這些點(diǎn)相關(guān)的三角形外接圓圓心，并連接外接圓圓心，得到Voronoi圖。最終效果如圖3所示。

圖3　生成的Voronoi圖

4　結(jié)束語

根據(jù)逐點(diǎn)插入法進(jìn)行Delaunay三角剖分得到Delaunay三角網(wǎng)是一種最為簡潔快速的方法，避免了諸如分治法等算法的復(fù)雜性，盡管時(shí)間耗費(fèi)相對(duì)加長，但現(xiàn)代計(jì)算機(jī)的進(jìn)步完全彌補(bǔ)了這一缺陷。經(jīng)本實(shí)驗(yàn)驗(yàn)證，由逐點(diǎn)插入生成Delaunay三角網(wǎng)，進(jìn)而生成Voronoi圖的方法切實(shí)可行。

[1]劉金義,劉爽.Voronoi圖應(yīng)用綜述[J].工程圖學(xué)學(xué)報(bào),2004,25(2): 125-132.

[2]俞亞磊.GIS中Delaunay三角網(wǎng)與Voronoi圖的相關(guān)問題研究[D].蕪湖:安徽師范大學(xué),2013.

[3]鮑蕊娜.離散點(diǎn)生成不規(guī)則三角網(wǎng)算法研究及實(shí)現(xiàn)[D].昆明:昆明理工大學(xué),2012.

[4]紀(jì)志浩,于明旭.基于點(diǎn)云數(shù)據(jù)三維重建方法的研究[J].黑龍江工程學(xué)院學(xué)報(bào),2014(3):7-9.

[5]宗大偉.Voronoi圖及其應(yīng)用研究[D].南京:南京航空航天大學(xué),2006.

[6]袁子薇.Voronoi圖細(xì)分算法研究[D].杭州:浙江工業(yè)大學(xué),2013.

[7]任永功,廖士中.利用類Delaunay三角剖分實(shí)現(xiàn)Voronoi圖[J].計(jì)算機(jī)科學(xué),2002,29(9):78-79.

[8]劉少華,羅小龍,何幼斌,等.基于Delaunay三角網(wǎng)的泰森多邊形生成算法研究[J].長江大學(xué)學(xué)報(bào),2007,4(1):10-103.

[9]卓中文,王山東,魏生文,等.基于Delaunay三角網(wǎng)生成Voronoi爆破圖的研究[J].現(xiàn)代礦業(yè),2011(12): 106-108.

[10]孫繼忠,胡艷,馬永強(qiáng).基于Delaunay三角剖分生成Voronoi圖算法[J].計(jì)算機(jī)應(yīng)用,2010,30(1):75-77.

[11]沈璐,宋曉東,鄧宇.VC 環(huán)境下Delaunay 三角剖分算法的設(shè)計(jì)及實(shí)現(xiàn)[J].吉林建筑工程學(xué)院學(xué)報(bào),2012,29(6):46-48.

[12]劉云,夏興東,黃北生.基于分治算法與逐點(diǎn)插入法的Delaunay三角網(wǎng)建立算法的改進(jìn)[J].現(xiàn)代測繪,2010(4):14-16.

[13]郭曉東.Delaunay三角形網(wǎng)絡(luò)逐點(diǎn)插入法的優(yōu)化算法[J].氣象與環(huán)境科學(xué),2014,37(2):112-116.

[14]王龍浩,王解先.基于逐點(diǎn)插入法的Delaunay三角網(wǎng)快速生成算法[J].工程勘察,2013,10:75-79.

[15]畢碩本,陳東祺,顏堅(jiān),等.基于二維凸殼的平面點(diǎn)集Delaunay三角網(wǎng)算法[J].計(jì)算機(jī)科學(xué),2004,41(10): 317-320.

[責(zé)任編輯：郝麗英]

Research and implementation of Voronoi diagram generation algorithm based on point by point insertion method

ZHANG Yan，LI Qiang

(College of Geoscience and Surveying Engineering,China University of Mining & Technology,Beijing 10083,China)

Based on point by point insertion method,the Voronoi diagram needs to generate the Delaunay triangulation first in order to meet the efficiency requirement of constructing Voronoi diagram quickly with a number of discrete point data.In the paper Lawson algorithm is used to carry on the LOP optimization in the process of forming a triangulation network to generate a reliable Delaunay triangulation.The relation of mutual duality between Delaunay triangulation and Voronoi diagram is used to construct the desired Voronoi map.After testing a number of random discrete data and comparing with the results of the standard result,this paper obtains a result that in addition to some abnormal conditions,this algorithm can quickly and accurately frame the targetted Voronoi map.

delaunay triangulation; LOP optimization; Voronoi diagram; incremental insertion algorithm

10.19352/j.cnki.issn1671-4679.2016.05.007

2016-03-28

張艷(1991-)，女，碩士研究生，研究方向：煤矸石山溫度場探測.

TP301.6

A

1671-4679(2016)05-0022-03