基于直接剖分的球面四边形离散格网生成方法

陈永就，林 川

（1.广东省国土资源测绘院，广东 广州510500）

基于直接剖分的球面四边形离散格网生成方法

陈永就1，林 川1

（1.广东省国土资源测绘院，广东 广州510500）

提出一种基于直接剖分的球面四边形离散网格生成方法，将该方法生成的四边形网格与基于QTM（四元三角网）扩展的四边形网格的面积形变进行对比分析。根据实验数据可知，基于QTM扩展的四边形网格最大与最小面积比值随着剖分层次的增加而增大，最后会收敛到2.1；基于直接剖分的球面四边形离散网格最大与最小面积比值随着剖分层次的增加而增大，且不收敛，但此网格在中间恒定、连续的大片区域，网格最大与最小面积比值随着剖分层次的增加最终收敛到1.3。

球面离散网格 ；四边形网格；直接剖分法；面积形变

全球离散网格模型是一种可以无限细分并且不会改变形状的地球球面拟合网格，当其细分到一定分辨率时，可以对地球的表面进行模拟，它能有效避免传统的经纬度网格在表达全球数据时产生的面积形变和断裂等问题[1,2]。剖分单元作为全球离散网格的基本单元，是网格的重要研究对象。目前国内外学者对网格单元的研究主要集中在三角形、四边形、六边形等，不同多边形网格具有各自的优点和缺点。Sadourny在1972年提出了四边形球面网格，发现基于正六面体的剖分边界误差比较大。之后许多学者对该网格进行了改进，其中最具代表性的是Nairetal采用Galerkin方法在四边形球面网格上使用浅水方程进行数值模拟，得到了非常理想的结果。三角形两两合并能很方便地得到四边形[3]，目前对球面四边形网格的研究大多是在三角网合并的基础上进行的，例如赵学胜[4]等在QTM的基础上，以上下2个三角形合并为一个四边形，构建出全球离散格网层次模型。直接合并的方法生成的四边形网格会继承原三角网的几何形变特性，本文拟通过直接剖分的方法产生球面四边形，通过网格面积形变这一种重要的网格质量评价标准[5]对基于直接剖分产生的球面四边形网格和基于QTM扩展的四边形网格进行对比分析。

1 球面四边形网格的构建

球面多边形网格一般是在多面体剖分的基础上建立的[6]，本文以正八面体剖分为例对两种网格进行分析。球内接正八面体和球面相交的6个点是南北两个极点和赤道上的4个点，它的12条边线映射到球面上即构成了球面基础网格，网格将球表面分成了8个相等的区域，以南北相邻的2个三角面组成的区域为例进行分析，其他球面的情况类似。在确立基础网格后便是对其采用一定的数学规则进行递归细分，不同的细分方法将产生不同的网格。

基于QTM扩展四边形网格的剖分方法：取3条边的中点（大圆弧的中点）两两相连，即将三角面剖分成4个小三角面。将球面两点之间的最短距离作为剖分线，这条线等同于两点间的大圆弧劣弧，用相同的方法进行细分直至所需的分辨率，最后将剖分所得的边相邻的南北两个三角网格两两合并成四边形网格[1]。

基于直接剖分的球面四边形离散网格的剖分方法：取四边形4条边上的4个中点（大圆弧的中点），四边形相对2条边上的中点相连，在球面上取两点间大圆弧的劣弧，即将初始的四边形剖分成4个子四边形，可以以相同的方法不断细分。

2 网格的可视化效果

本文使用OSG(OpenSceneGraph)实现了两种剖分方案下的球面四边形网格的可视化（以1/4半球为例，其他球面的情况类似）。图1显示的是4次剖分后的QTM扩展四边形网格，可以明显看出该网格中间的网格面积较大；图2显示的是直接剖分方法生成的球面四边形，由于四边形的4个点并不在同一个平面上，因此OSG在显示时是以三角网的形式。与基于QTM扩展四边形网格相比，直接剖分法生成的四边形网格更紧致，但是最大四边形网格单元与最小四边形网格单元面积相差非常大。

3 网格的面积形变

网格质量的评判标准之一是网格单元的近似均等性。由球面几何空间的性质可知，不可能做到把球面分割成完全均匀相等的网格，因此所有的剖分方法目的是使网格单元能够尽量均等。四边形网格单元面积是指网格在球面上围成的表面积，可以看成是由2个三角形组成。球面三角形的面积计算公式如下[7]：

其中，x1、 x2、 x3分别是三角形3个顶点的向量。

图1 QTM扩展四边网格

图2 直接剖分法生成的四边形网格

图3 50%较大面积网格的分布情况（6层）

图4 50%较大面积网格的分布情况（7层）

在对单位三角形一分为四时，QTM网格中间三角形的面积明显比周边三角形面积大，基于QTM扩展的四边形网格会继承QTM网格的形变规律。从直接剖分法生成的四边形网格的可视化效果来看，网格的面积形变主要集中在边缘部分，网格中间大片连续的区域较为均匀，这部分区域网格单元的面积较大。将各个剖分层次中的50%较大面积网格用颜色标出，可以看出这部分网格区域是连续的且范围不会随着剖分层次的增加而发生明显改变。图3、图4分别显示的是直接剖分法下6层剖分和7层剖分的网格，红色标识的是网格总数中50%较大面积网格。

对直接剖分下网格总数中50%较大面积网格、整体网格和QTM扩展的四边形网格进行对比，求出它们在各个剖分层次的最大与最小网格面积。研究区域中最大单元网格面积和最小单元网格面积的比值越小，说明网格大小越接近，网格越均匀。通过对网格最大与最小面积比值在各个剖分层次变化的统计分析，得到网格均匀性特征随剖分层次增加的变化趋势，若变化收敛，则网格均匀性特征稳定。表1显示的是上述四边形网格最大与最小面积比值在各个剖分层次的变化。

由上表数据可知，基于QTM扩展的四边形网格最大与最小面积比值随着剖分层次的增加而增大，最后会收敛到2.1。基于直接剖分的球面四边形离散网格最大与最小面积比值随着剖分层次的增加而增大，且不收敛。通过对单元网格面积的统计结果可得出，是由于剖分层次增加后网格边缘四边形面积骤减导致的。直接剖分下网格总数中50%较大面积网格的最大与最小面积比值随着剖分层次的增加最终收敛到1.3。从全球网格分布来看，基于QTM扩展的四边形网格面积形变要优于直接剖分法所得网格，从区域网格分布来看，直接剖分法所得网格在中间恒定、连续的大片区域上网格细分更加规整和均匀。

表1 网格最大与最小面积比值在各个剖分层次的变化

4 结 语

基于三角形扩展的四边形网格会继承三角形网格的形变特征，本文提出了一种基于直接剖分的球面四边形离散网格生成方法与基于QTM扩展的四边形网格相比，它在整体上均匀性较差，但在大范围的局部区域上表现出更加规整和均匀的特性，满足一般中小尺度模型的范围要求。基于直接剖分的球面四边形离散网格为构建局部高精度网格提出了新的参考，其在球面离散网格建模中的应用值得进一步研究。

[1] 赵学胜，侯妙乐，白建军. 全球离散格网的空间数字建模[M].北京:测绘出版社，2007

[2] 李德仁，朱欣焰，龚健雅. 从数字地图到空间信息格网[J].武汉大学学报：信息科学版， 2003,28(6):642-650

[3] Sahr K, White D, Kimeling A. Geodesic Discrete Global Grid Systems[J].Cartography and Geographic Information Science, 2003,30(2):121-134

[4] 赵学胜，白建军. 基于菱形块的全球离散格网层次建模[J].中国矿业大学学报，2007(3):397-401

[5] Goodchild M F. Criteria for Evaluation of Global Grid Models for Environmental Monitoring and Analysis[R].Ncgia Technical Report,1994

[6] 张永生，贲进，童晓冲. 地球空间信息球面离散网格——理论算法及应用[M] . 北京：科学出版社，2007

[7] 赵学胜，孙文彬，陈军. 基于QTM的全球离散格网形变分布及收敛分析[J].中国矿业大学学报,2005,30(4):438-442

图3 图像提取边界

图4 边界点云数

图5 特征线

图6 平面点提取结果

6 结 语

本文在扫描线和区域生长方法的基础上，提出按照特征线的点云数据分割方法。

1）验证了这种方法在点云分割过程中的正确性和有效性，按照特征线进行数据分割，并拟合出最佳平面，为点云的数据分割提供一种新的方法。

2）本文为点云数据分割提供了一个新的思考方向。在分割过程中，如何更好地提取深度图像的边缘信息可以进一步研究。

参考文献

[1] 蔡润彬,地面激光扫描数据后处理若干关键技术研究[D].上海:同济大学，2008

[2] Jiang X Y, Bunke H. Edge Detection in Range Images Based on Scan Line Approximation[J]. Computer Vision and Image Understanding, 1999,73(2):183-199

[3] Besl P J, Jain R C. Segmentation Through Variable-order Surface Fitting[J].IEEE Transactionson Pattern Analysis and Machine Intelligence, 1988, 10(2):167-192

[4] 向日华, 王润生. 一种基于高斯混合模型的距离图像分割算法[J]. 软件学报, 2003, 14(7): 1 250-1 257

[5] Yokoya N, Levine M D. Range Image Segmentation Based on Differential Geometry: A Hybrid Approach [J]. IEEE Trans Pami, 1989, 11(6): 643-649

[6] 丁益洪, 平西建, 胡敏. 基于随机 Hough 变化的深度图像分割 [J]. 计算机辅助设计与图形学学报, 2005, 17(5): 902-907

[7] 何丽，李嘉，郑德华.基于栅格的点云数据的边界探测方法[J].测绘工程，2013，22(3):69-73

第一作者简介：张大鹏，硕士，研究方向为三维激光扫描技术。

P208

B

1672-4623（2015）03-0130-03

10.3969/j.issn.1672-4623.2015.03.045

陈永就，工程师，主要从事大地测量、工程测量及地理信息系统的应用和软件开发工作。

2015-01-13。