使用Voronoi圖對流場拓撲區域進行劃分

馬玉潔

?

使用Voronoi圖對流場拓撲區域進行劃分

馬玉潔

（商丘師范學院計算機科學系，河南商丘476000）

特征可視化中的拓撲結構分析法，能夠快速的顯示流場的全局結構，在側重于考慮流場的特殊結構時顯示出了較大的優越性。但是在很多情況下，僅僅顯示流場的結構還不夠，還需要更詳細的知道拓撲場中每個區域的作用范圍。傳統的方法都是根據特征矢量的虛部來判斷拓撲區域的作用范圍，這種方法太過于概括，區域大小只是相對的，沒有考慮到附近臨界點對周圍流體運動的影響。為了能更真實的反映臨界點對周圍流運動的影響，論文提出使用Voronoi圖來劃分拓撲區域的作用范圍，并將該方法應用于海洋流場。同時也與傳統的特征矢量方法進行了對比，實驗表明，取得了較好的效果。

特征可視化；海洋流場；拓撲區域；Voronoi圖

在流場可視化中，拓撲結構分析法是一種從全局了解矢量場結構的新技術，它是一種全局圖標的構造和映射方法。拓撲可視化法將流場中精確的定量的信息用一種簡單的圖表描繪出來，該方法直觀簡潔，是重要而且比較成功的特征可視化方法。矢量場的拓撲結構抽取了矢量場的主要結構，忽略了其它次要的信息。但是，在實際應用中，僅僅顯示流場的結構還不夠，還需要更詳細的知道拓撲場中每個區域的作用范圍。傳統的方法都是根據特征矢量的虛部來判斷拓撲區域的作用范圍，這種方法太過于概括，區域大小只是相對的，沒有考慮到附近臨界點對周圍流體運動的影響。因此，需要尋求一種新的方法來劃分拓撲區域。

Voronoi圖是計算幾何的重要研究內容，它是關于空間鄰近關系的一種基礎數據結構。一直以來，許多人都對它進行過研究并應用在包括天文、地理、生物、以及網絡等許多領域。比如在地理上可以用Voronoi圖來分析城市影響的范圍，在網絡上可以用來表示無線網絡的路由選擇等。

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

1 拓撲結構分析法

矢量場拓撲結構分析法是由Helman and Hesselink提出的，它是建立在臨界點理論基礎之上的。一個矢量場的拓撲由臨界點和連接臨界點的積分曲線或曲面組成，它使用流線連接臨界點，把流場分為不同的區域。臨界點是流場中那些速度為零的點，臨界點附近矢量場的特性由臨界點矢量對其位置矢量的偏導數矩陣Jacobian（雅可比矩陣）決定，即

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

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

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

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

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

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

矢量場拓撲結構的分析和可視化由以下幾步組成：臨界點位置的計算、對臨界點進行分類、計算積分曲線或曲面。具體的實現步驟在參考文獻[7]中有詳盡的描述。

2 Voronoi圖的定義及構造方法

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

Voronoi圖的構造有很多成熟的算法，比如增量法、分治法以及波面傳播算法等。這里使用最經典的分治法來構造Voronoi圖。分治法求Voronoi圖大致分為2步：① 對中的點按其坐標排序；② 調用子程序Voronoi()。而子程序Voronoi()的實現步驟為：

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

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

（3）若|_|≤3，產生及輸出Vor(_)，轉4。否則，調用Voronoi(_)；

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

（5）返回。

3 使用Voronoi圖劃分拓撲區域

3.1 理論依據

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

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

3.2 應用于海洋流場

該算法的實現分為求拓撲圖像和對臨界點求Voronoi圖兩步。先對某一特定海洋流場求拓撲圖像，使用拓撲結構分析法所得到的圖像如圖1所示。該區域大約有5000個采樣數據點(=5000)，該區域總共有26個臨界點，其中包括13個鞍點和13非鞍點。

圖1 特定海洋流場的拓撲圖像

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

3.3 與傳統特征矢量方法得到的圖像對比

傳統劃分拓撲區域的方法是特征矢量法，是根據特征矢量的虛部的大小顯示出的旋渦的影響范圍（只是相對的），如圖3所示。圖3中的背景是用線積分卷積法得到的流場圖像；藍色和紅色的點是根據特征矢量方法檢測出的渦核的位置，而它們周圍的圓是根據特征矢量的虛部的大小顯示出的旋渦的影響范圍。顏色代表方向，紅色代表旋渦旋轉的方向是順時針，藍色的則代表逆時針方向。

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

圖2 使用Voronoi圖劃分拓撲圖像

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

4 結論

論文使用Voronoi圖來進行拓撲區域的劃分，在劃分時同時考慮了附近臨界點對周圍流的影響，使得劃分更為科學。并將該方法應用于特定的海洋流場，同時與特征矢量方法劃分渦核區域進行了比較，實驗表明取得了較好的效果。進一步的研究內容可以根據Voronoi圖的局域動態特性，考慮先對拓撲圖像進行簡化，先合并臨界點，臨界點之間合并之后，只需局部重構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 圖在蜂窩制移動通信系統中的應用[J]. 電子技術, 2002, 29(1): 37-39.

[5] 閆衛陽, 郭慶勝, 李圣權. 基于加權Voronoi 圖的城市經濟區劃分方法探討[J]. 華中師范大學學報(自然科學版), 2003, 37(4): 567-571.

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

[7] 馬玉潔. 基于海洋流場的多級拓撲可視化[J]. 陜西理工學院學報(自然科學版), 2010, 26(1): 54-57.

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

[9] 陳麗娜, 楊冠杰. 快速檢測流場中渦核區域的角度函數法[J]. 工程圖學學報, 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）；河南省政府決策研究招標課題資助項目（B546）

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