馬玉潔

?

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

馬玉潔

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）用垂線劃分成兩個(gè)尺寸大致相等的子集_，_，使_內(nèi)的全體點(diǎn)位于的左側(cè)，_內(nèi)的全體點(diǎn)位于的右側(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圖具有勢(shì)力范圍性質(zhì)(Influence Region)和局域動(dòng)態(tài)特性(Local Dynamization)。對(duì)一個(gè)空間生長(zhǎng)目標(biāo)而言，凡落在其Voronoi區(qū)域范圍內(nèi)的空間點(diǎn)均距其最近，因此該Voronoi區(qū)域在一定程度上反應(yīng)了空間生長(zhǎng)目標(biāo)的影響范圍，或者稱勢(shì)力范圍。而局域動(dòng)態(tài)特性是指刪除或增加一個(gè)空間生長(zhǎng)目標(biāo)，只影響相鄰的空間生長(zhǎng)目標(biāo)，換言之，對(duì)Voronoi圖的修改只影響局部范圍。

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

論文使用Voronoi圖來(lái)進(jìn)行拓?fù)鋮^(qū)域的劃分，在劃分時(shí)同時(shí)考慮了附近臨界點(diǎn)對(duì)周圍流的影響，使得劃分更為科學(xué)。并將該方法應(yīng)用于特定的海洋流場(chǎng)，同時(shí)與特征矢量方法劃分渦核區(qū)域進(jìn)行了比較，實(shí)驗(yàn)表明取得了較好的效果。進(jìn)一步的研究?jī)?nèi)容可以根據(jù)Voronoi圖的局域動(dòng)態(tài)特性，考慮先對(duì)拓?fù)鋱D像進(jìn)行簡(jiǎn)化，先合并臨界點(diǎn)，臨界點(diǎ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 圖在蜂窩制移動(dòng)通信系統(tǒng)中的應(yīng)用[J]. 電子技術(shù), 2002, 29(1): 37-39.

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

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

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

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

[9] 陳麗娜, 楊冠杰. 快速檢測(cè)流場(chǎng)中渦核區(qū)域的角度函數(shù)法[J]. 工程圖學(xué)學(xué)報(bào), 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

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

馬玉潔（1969-），女，河南睢縣人，副教授，主要研究方向?yàn)榭茖W(xué)計(jì)算可視化等。