使用Voronoi圖對流場拓?fù)鋮^(qū)域進(jìn)行劃分

馬玉潔

?

使用Voronoi圖對流場拓?fù)鋮^(qū)域進(jìn)行劃分

馬玉潔

（商丘師范學(xué)院計算機(jī)科學(xué)系，河南商丘476000）

特征可視化中的拓?fù)浣Y(jié)構(gòu)分析法，能夠快速的顯示流場的全局結(jié)構(gòu)，在側(cè)重于考慮流場的特殊結(jié)構(gòu)時顯示出了較大的優(yōu)越性。但是在很多情況下，僅僅顯示流場的結(jié)構(gòu)還不夠，還需要更詳細(xì)的知道拓?fù)鋱鲋忻總€區(qū)域的作用范圍。傳統(tǒng)的方法都是根據(jù)特征矢量的虛部來判斷拓?fù)鋮^(qū)域的作用范圍，這種方法太過于概括，區(qū)域大小只是相對的，沒有考慮到附近臨界點對周圍流體運動的影響。為了能更真實的反映臨界點對周圍流運動的影響，論文提出使用Voronoi圖來劃分拓?fù)鋮^(qū)域的作用范圍，并將該方法應(yīng)用于海洋流場。同時也與傳統(tǒng)的特征矢量方法進(jìn)行了對比，實驗表明，取得了較好的效果。

特征可視化；海洋流場；拓?fù)鋮^(qū)域；Voronoi圖

在流場可視化中，拓?fù)浣Y(jié)構(gòu)分析法是一種從全局了解矢量場結(jié)構(gòu)的新技術(shù)，它是一種全局圖標(biāo)的構(gòu)造和映射方法。拓?fù)淇梢暬▽⒘鲌鲋芯_的定量的信息用一種簡單的圖表描繪出來，該方法直觀簡潔，是重要而且比較成功的特征可視化方法。矢量場的拓?fù)浣Y(jié)構(gòu)抽取了矢量場的主要結(jié)構(gòu)，忽略了其它次要的信息。但是，在實際應(yīng)用中，僅僅顯示流場的結(jié)構(gòu)還不夠，還需要更詳細(xì)的知道拓?fù)鋱鲋忻總€區(qū)域的作用范圍。傳統(tǒng)的方法都是根據(jù)特征矢量的虛部來判斷拓?fù)鋮^(qū)域的作用范圍，這種方法太過于概括，區(qū)域大小只是相對的，沒有考慮到附近臨界點對周圍流體運動的影響。因此，需要尋求一種新的方法來劃分拓?fù)鋮^(qū)域。

Voronoi圖是計算幾何的重要研究內(nèi)容，它是關(guān)于空間鄰近關(guān)系的一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。一直以來，許多人都對它進(jìn)行過研究并應(yīng)用在包括天文、地理、生物、以及網(wǎng)絡(luò)等許多領(lǐng)域。比如在地理上可以用Voronoi圖來分析城市影響的范圍，在網(wǎng)絡(luò)上可以用來表示無線網(wǎng)絡(luò)的路由選擇等。

在大多數(shù)情況下，流場中存在不止一個臨界點，臨界點之間的流體運動是由多個臨界點共同決定的。單獨臨界點周圍流體的運動比較簡單，但這種情況只是理想情況，因為大多情況下，臨界點周圍的流體的運動要同時受多個臨界點的影響，因此每個臨界點都有其對應(yīng)的影響范圍。而Voronoi圖勢力范圍性質(zhì)和局域動態(tài)態(tài)性，所以這里使用Voronoi圖來對流場的拓?fù)鋮^(qū)域進(jìn)行劃分，并應(yīng)用于海洋流場，同時跟傳統(tǒng)的特征矢量方法做了對比，實驗證明取得了較好的效果。

1 拓?fù)浣Y(jié)構(gòu)分析法

矢量場拓?fù)浣Y(jié)構(gòu)分析法是由Helman and Hesselink提出的，它是建立在臨界點理論基礎(chǔ)之上的。一個矢量場的拓?fù)溆膳R界點和連接臨界點的積分曲線或曲面組成，它使用流線連接臨界點，把流場分為不同的區(qū)域。臨界點是流場中那些速度為零的點，臨界點附近矢量場的特性由臨界點矢量對其位置矢量的偏導(dǎo)數(shù)矩陣Jacobian（雅可比矩陣）決定，即

這里下標(biāo)指的是偏導(dǎo)，臨界點是根據(jù)復(fù)特征值來分類的，假定臨界點是雙曲的，也就是說，特征值的實部非零，那么可以將臨界點分為5類（中心點是非雙曲型的臨界點，這里不再考慮）：

·鞍 點()：特征值的虛部為0，且實部互為相反數(shù)，即：1=2=0，1*2<0；

· 排斥結(jié)點()：特征值的虛部為0，且實部都是正的，即：1=2=0，1>0，2>0；

· 吸引結(jié)點()：特征值的虛部為0，且實部都是負(fù)的，即：1=2=0，1<0，2<0；

· 排斥焦點()：特征值是共額復(fù)數(shù)，且實部都是正的，即：1=2≠0，1>0，2>0；

· 吸引焦點()：特征值是共額復(fù)數(shù)，且實部都是負(fù)的，即：1=2≠0，1<0，2<0；

矢量場拓?fù)浣Y(jié)構(gòu)的分析和可視化由以下幾步組成：臨界點位置的計算、對臨界點進(jìn)行分類、計算積分曲線或曲面。具體的實現(xiàn)步驟在參考文獻(xiàn)[7]中有詳盡的描述。

2 Voronoi圖的定義及構(gòu)造方法

Voronoi圖的定義最早是針對平面上的點集而定義的，它把平面分成若干個區(qū)域，每個點對應(yīng)一個區(qū)域。該點的這個區(qū)域是由比集合中的其它點更接近此點的所有點所共同組成的。具體為：設(shè)={，，…，P}∈為平面上的個點的集合，P，P為平面上的任意兩點，且≠，稱(P)=∩(P，P)為關(guān)于P的Voronoi多邊形，則它一定滿足(P)={∈‖-P‖≤‖-P‖,≠，=1，2，3，…，}，點集的Voronoi圖Vor()定義為點集中所有點的Voronoi多邊形的并，即：Vor()=∪(P)。因此，平面上的Voronoi 圖可以看作是以點集中的每個點作為生長核以相同的速度向外擴(kuò)張，直到彼此相遇為止而在平面上所形成的圖形。這樣，除最外層的點形成開放的區(qū)域外，其余每個點都形成凸多邊形。

Voronoi圖的構(gòu)造有很多成熟的算法，比如增量法、分治法以及波面?zhèn)鞑ニ惴ǖ?。這里使用最經(jīng)典的分治法來構(gòu)造Voronoi圖。分治法求Voronoi圖大致分為2步：① 對中的點按其坐標(biāo)排序；② 調(diào)用子程序Voronoi()。而子程序Voronoi()的實現(xiàn)步驟為：

（1）用垂線劃分成兩個尺寸大致相等的子集_，_，使_內(nèi)的全體點位于的左側(cè)，_內(nèi)的全體點位于的右側(cè)。=∪；

（2）若|_|≤3，產(chǎn)生及輸出Vor(_)。否則，調(diào)用Voronoi(_)；

（3）若|_|≤3，產(chǎn)生及輸出Vor(_)，轉(zhuǎn)4。否則，調(diào)用Voronoi(_)；

（4）合并Vor(_)及 Vor(_得到Vor()，輸出Vor()；

（5）返回。

3 使用Voronoi圖劃分拓?fù)鋮^(qū)域

3.1 理論依據(jù)

Voronoi圖具有勢力范圍性質(zhì)(Influence Region)和局域動態(tài)特性(Local Dynamization)。對一個空間生長目標(biāo)而言，凡落在其Voronoi區(qū)域范圍內(nèi)的空間點均距其最近，因此該Voronoi區(qū)域在一定程度上反應(yīng)了空間生長目標(biāo)的影響范圍，或者稱勢力范圍。而局域動態(tài)特性是指刪除或增加一個空間生長目標(biāo)，只影響相鄰的空間生長目標(biāo)，換言之，對Voronoi圖的修改只影響局部范圍。

把臨界點當(dāng)作空間生長目標(biāo)，對流場進(jìn)行Voronoi圖劃分，就可以得到每個臨界點的影響范圍，位于一個臨界點Voronoi區(qū)域內(nèi)的流體運動特性主要由該臨界點的類型決定，Voronoi區(qū)域的尺寸就是其包含臨界點的近似影響范圍，邊界附近的流體運動特性由相鄰的臨界點類型共同決定。

3.2 應(yīng)用于海洋流場

該算法的實現(xiàn)分為求拓?fù)鋱D像和對臨界點求Voronoi圖兩步。先對某一特定海洋流場求拓?fù)鋱D像，使用拓?fù)浣Y(jié)構(gòu)分析法所得到的圖像如圖1所示。該區(qū)域大約有5000個采樣數(shù)據(jù)點(=5000)，該區(qū)域總共有26個臨界點，其中包括13個鞍點和13非鞍點。

圖1 特定海洋流場的拓?fù)鋱D像

使用Voronoi圖進(jìn)行區(qū)域劃分之后的圖像如圖2所示。紅色線是根據(jù)對臨界點用分治法得到的Voronoi圖，從圖中可以看到，Voronoi圖較好地對拓?fù)鋱D像進(jìn)行了合理的劃分，這種劃分同時考慮了附近臨界點對周圍流體的影響。

3.3 與傳統(tǒng)特征矢量方法得到的圖像對比

傳統(tǒng)劃分拓?fù)鋮^(qū)域的方法是特征矢量法，是根據(jù)特征矢量的虛部的大小顯示出的旋渦的影響范圍（只是相對的），如圖3所示。圖3中的背景是用線積分卷積法得到的流場圖像；藍(lán)色和紅色的點是根據(jù)特征矢量方法檢測出的渦核的位置，而它們周圍的圓是根據(jù)特征矢量的虛部的大小顯示出的旋渦的影響范圍。顏色代表方向，紅色代表旋渦旋轉(zhuǎn)的方向是順時針，藍(lán)色的則代表逆時針方向。

對比圖2和圖3可以看到，使用Voronoi圖可以更好的劃分出流的作用范圍，而特征矢量方法的劃分則比較粗略，而且這種劃分還是相對的。實驗表明，Voronoi圖由于考慮了附近臨界點對周圍流的影響，所以劃分更加科學(xué)。

圖2 使用Voronoi圖劃分拓?fù)鋱D像

圖3 特征矢量法劃分渦流作用范圍

4 結(jié)論

論文使用Voronoi圖來進(jìn)行拓?fù)鋮^(qū)域的劃分，在劃分時同時考慮了附近臨界點對周圍流的影響，使得劃分更為科學(xué)。并將該方法應(yīng)用于特定的海洋流場，同時與特征矢量方法劃分渦核區(qū)域進(jìn)行了比較，實驗表明取得了較好的效果。進(jìn)一步的研究內(nèi)容可以根據(jù)Voronoi圖的局域動態(tài)特性，考慮先對拓?fù)鋱D像進(jìn)行簡化，先合并臨界點，臨界點之間合并之后，只需局部重構(gòu)Voronoi圖即可。

[1] Helman J L, Hesselink L. Visualizing vector field topology in fluid flows [J]. IEEE Computer Graphics and Applications, 1991, 11(3): 36-46.

[2] Helman J L, Hesselink L. Surface representation of two- and three-dimensional fluid flow topology [C]// Proceedings Visualization '90, IEEE Computer Society Press, Los Alamitos, CA, 1990: 6-13.

[3] W de Leeuw, R van Liere. Multi-level topology for flow visualization [J]. Computers & Graphics, 2000, 24(3): 325-331.

[4] 尚志恩, 徐 寧. Voronoi 圖在蜂窩制移動通信系統(tǒng)中的應(yīng)用[J]. 電子技術(shù), 2002, 29(1): 37-39.

[5] 閆衛(wèi)陽, 郭慶勝, 李圣權(quán). 基于加權(quán)Voronoi 圖的城市經(jīng)濟(jì)區(qū)劃分方法探討[J]. 華中師范大學(xué)學(xué)報(自然科學(xué)版), 2003, 37(4): 567-571.

[6] 周培德. 計算幾何——算法分析與設(shè)計[M]. 北京:清華大學(xué)出版社, 2000. 88-130.

[7] 馬玉潔. 基于海洋流場的多級拓?fù)淇梢暬痆J]. 陜西理工學(xué)院學(xué)報(自然科學(xué)版), 2010, 26(1): 54-57.

[8] 陳麗娜, 馬玉潔. 基于平面點集的Voronoi圖的近似構(gòu)造[J]. 微計算機(jī)信息, 2007, 23(27): 263-264.

[9] 陳麗娜, 楊冠杰. 快速檢測流場中渦核區(qū)域的角度函數(shù)法[J]. 工程圖學(xué)學(xué)報, 2008, 29(1): 146-149.

Division of Flow Field Topological Regions through Voronoi Diagram

MA Yu-jie

( Department of Computer Science, Shangqiu Normal University, Shangqiu Henan 476000, China )

Topology analysis method of feature-based visualization can show quickly the overall structure of flow field, and is of a greater superiority in focusing on the special structure of the flow field. However, in many cases, it is not enough to only show the structure of the flow field, we also want to know the topological region in detail. Traditional methods to determine the topological region are based on the imaginary part of feature vector, but these approaches are too general, and, because the area size is only relative, it doesn’t consider the impact of the near critical points to the surrounding fluid. In order to show truly the impact of the critical points to around flow movement, Voronoi diagram is proposed to divide the topological region, and the method has been applied to ocean flow fields. Compared to the traditional feature vectors method and proved through experiments, it can achieve better results.

feature-based visualization; ocean flow field; topological region; Voronoi diagram

TP 391

A

1003-0158(2011)03-0082-04

2010-10-24

河南省科技廳資助項目（112300410210）；河南省政府決策研究招標(biāo)課題資助項目（B546）

馬玉潔（1969-），女，河南睢縣人，副教授，主要研究方向為科學(xué)計算可視化等。