使用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-），女，河南睢县人，副教授，主要研究方向为科学计算可视化等。