基于QTM的全球离散格网变形分布及收敛分析.pdf

第3 4 卷第4 期 2 0 0 5 年7 月 中国矿业大学学报 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y V 0 1 ．3 4N o ．4 J u l ．2 0 0 5 文章编号1 0 0 0 1 9 6 4 2 0 0 5 0 4 0 4 3 8 0 5 基于Q T M 的全球离散格网变形分布及收敛分析 赵学胜1 ’2 ，孙文彬1 ，陈军2 1 ．中国矿业大学资源与安全工程学院，北京1 0 0 0 8 3 ； 2 ．国家基础地理信息中心，北京1 0 0 0 4 4 摘要介绍了球面四元三角网 Q T M 的剖分原理；用纬线代替大圆弧线以改进Q T M 的传统细 化方法，既减小了格网的变形量，又提高了格网数据与地理坐标的转换效率；根据实验数据，分析 了在不同层次Q T M 格网中其面积和边长的变异性分布特征．结果表明随着剖分层次的增加， 1 格网面积的变形特征逐渐接近于正态分布；2 三角形最大／最小面积的比值和最大／最小边长 的比值越来越大，但其增长速度越来越小，最终收敛到1 ．7 3 和1 ．8 6 ． 关键词地理信息系统；四元三角网；变形分布；收敛特征；全球离散格网 中圈分类号P2 0 8文献标识码A D i s t o r t i o nD i s t r i b u t i o na n dC o n v e r g e n tA n a l y s i s o ft h eG l o b a lD i s c r e t eG r i dB a s e do nQ T M Z H A OX u e s h e n 9 1 ”。S U NW e n b i n l ，C H E NJ u n 2 1 ．S c h o o lo fR e s o u r c e sa n dS a f e i t yE n g i n e e r i n g ， C h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ，B e i j i n g10 0 0 8 3 ，C h i n aI 2 ．N a t i o n a lG e o m a t i c sC e n t e ro fC h i n a ，B e i j i n g10 0 0 4 4 ，C h i n a A b s t r a c t T h ep a r t i t i o np r i n c i p l eo fQ T Mo ns p h e r ei si n t r o d u c e d ．I no r d e rt or e d u c et h ea r e ao r s h a p ed i s t o r t i o no fg r i d sa n dt oi m p r o v et h ec o n v e r s i o ne f f i c i e n c yb e t w e e ng r i dd a t aa n dg e o g r a p h i c c o o r d i n a t e s ，t h et r a d i t i o n a lm e t h o d so fQ T Mp a r t i t i o ni sm o d i f i e db yu s i n gl a t i t u d e l i n ei n s t e a do f c i r c l e l i n e ．T h e nt h ed i s t o r t i o nd i s t r i b u t i o nc h a r a c t e r si na r e a sa n de d g e so fg r i d sa r ea n a l y z e di n d e t a i lb a s e do ne x p e r i m e n t a ld a t a ．T h er e s u l ts h o w st h a tw i t ht h ei n c r e a s eo fp a r t i t i o nl e v e l s ，1 d i s t o r t i o nd i s t r i b u t i o nc h a r a c t e ri na r e a si Sc l o s et ot h en o r m a ld i s t r i b u t i o n ，a n d2 t h er a t i o so f S 。。。／S 。i 。a n dL 。。。／L 。i 。b e c o m eg r e a t e r ，b u tt h e i ri n c r e m e n t sa r el e s sa n dl e s s ，a tl a s tc o n v e r g i n gt o 1 ．7 3a n d1 ．8 6r e s p e c t i v e l y ． K e yw o r d s G I S ；Q T M ；d i s t o r t i o nd i s t r i b u t i o n ；c o n v e r g e n tc h a r a c t e r ；g l o b a ld i s c r e t eg r i d 全球离散格网模型是空间信息格网 S I G 及 网格计算 G C 的基础，目前已成为国际G I S 学术 界一个新的研究热点．球面四元三角网 Q T M Q u a t e r n a r yT r i a n g u l a rM e s h 是基于球面的一种可 以无限细分，但又不改变形状的地球体拟合格网， 它具有层次性和全球连续性特征，当细分到一定程 度时，可以达到模拟地球表面的目的，有望从根本 上解决平面格网模型在全球多尺度数据管理上的 数据断裂、变形和拓扑不一致性等问题[ 1 口] ．近年 来，尽管国内外学者对Q T M 格网剖分方法和实际 应用做了大量的工作，取得了可喜的进展．但是，目 前的研究都是把球面离散格网剖分作为全球空间 收稿日期2 0 0 4 一0 7 0 9 基金项目t 国家杰出青年基金 4 0 0 2 5 1 0 1 和国家自然科学基金 4 0 4 7 1 1 0 8 作者简介赵学胜 1 9 6 7 一 ，男，山东省曹县人。副教授，工学博士，从事G I S 理论与应用、全球多分辨率数据的操作与更新等方向的研 究． E - m a H Z X S c u m t b ．e d u ．c n 万方数据 第4 期赵学胜等基于Q T M 的全球离散格网变形分布及收敛分析4 3 9 数据层次索引和空间定位基础[ 3 ] ，而没有涉及球面 层次格网的几何变形分布规律及收敛阈值等问题， 即缺乏一个明确的量化指标来评价格网数据的计 算精度，直接影响了格网数据的质量和使用领域． 本文拟分析球面Q T M 的剖分原理；然后对原 有的Q T M 的细化方法进行改进，即三角形格网的 底边用纬线代替大圆弧线，更好地控制格网的变形 量和提高数据的转换效率；最后将详细分析格网几 何特征的变异性分布规律和收敛性阈值，为全球格 网数据的多分辨率操作提供Q T M 格网数据的计 算质量和使用范围． 1Q T M 格网的剖分原理及相关研究评述 若要构建全球离散空间，首先必须把球面剖分 成格网状．不同的球面剖分方法不但影响球面数据 的存储和管理效率，而且还影响全球G I S 的功能 操作，如邻近分析、空间查询、数据更新和三维可视 化等．目前最常用的球面剖分方法是把球体的内接 正多面体作为球面剖分的基础．如正四面体 4 个 等边三角形 、正六面体 6 个正方形 、正八面体 8 个三角形 、正十二面体 1 2 个五边形 和正二十面 体 2 0 个等边三角形 ．多面体的边投影到球面上 作为大圆弧段形成球面三角形 或四边形，五边形， 六边形 的边，覆盖整个球面，作为全球剖分的基 础．球面多边形是规则的，全部边和内角都相等． 若对球面多边形进一步细化，则球面多边形在 大小和形状上不可避免产生变形，即边和内角不 等．另一方面，实体在穿越单元边界之间的处理相 对比较复杂．所以在内接正多面体的选择上存在着 以下矛盾H 咕] * 内接正多面体一个面的面积越大，在任何 给定的细化层次上面积相差就越大；而穿越单元边 界的次数越少，边界处理比较简单． * 内接正多面体的面数越多，实体特性穿越 边界的次数越多，边界处理比较复杂；但是在任何 给定的细化层次上面积相差就相对较小． 近年来，许多学者根据不同的实际应用情况， 选择不同的内接多面体作为球面格网剖分的基础． 如基于八面体的有全球数据的层次结构模型[ 6 ] 、 连续索引模型[ 7 ] 、空间数据质量与层次综合模 型[ 1 - 4 ] 等；基于十二面体的有全球D E M 影像数据 压缩模型[ 8 1 等；基于二十面体的有全球层次数据 索引‘9 | 、全球导航模型‘1 0 ] 、全球格网定位系统m ] 等；基于类二十面体的有全球环境监测模型[ 1 2 ] 等． 总之，针对不同的应用领域，国内外学者取得 了比较丰富的研究成果．但是，从球面几何可知，没 有一种剖分方法能使球面格网在每个层次上，获得 象平面栅格那样完全相同的几何特征 如面积、长 度、角度 ，只能达到近似相等．那么，其近似程度如 何 面积和边长的变形又有哪些规律 是否收敛 目前对这些问题研究较少． 2Q T M 格网剖分的改进 本文所采用的Q T M 剖分，是选取球内切正八 面体作为球面格网划分的基础，主要是因为当按八 面体投影划分时，其顶点占据球面主要点 包括两 极 ，而边的投影则与赤道、主子午线和9 0 。、1 8 0 。、 2 7 0 。子午线重合．这样，很容易确定球面上的一个 点在八面体的哪一个投影面上，并且八面体的球面 格网与常用的球面经纬度格网很容易转化． 2 ．1传统Q T M 的层次剖分 为了对球面三角形进一步细化，D u t t o n [ 4 ] 是根 据顶点的经纬度坐标进行平均，产生三条边的中 点，把中点连线从球心向球面投影，即产生四个小 球面三角形，以此类推 如图1 ⋯，形成了不同层 次的全球Q T M 剖分格网．但这种细化方法存在两 个问题 1 格网的变形稍大从首次细化可以看出，中 间三角形的面积稍大，其他三个稍小，随着层次的 递归细化，中间三角形比其同层次的其他三角形， 变形积累也越来越大． 2 格网与地理坐标之间难以对应从首次细 化可以看出 如图l b ，上三角形的底边与纬线是 不符合的，这个特征使其很难直接确定球面上的一 个点在哪一个球面三角形上． ③◇◎◎ a 细化前彻首次细化 c 二次细化 d 三次细化 图1基于正八面体的球面层次剖分 F i g ．1 H i e r a r c h i c a lp a r t i t i o no fs p h e r i c a l f a c e tb a s e do no c t a h e d r o n 2 ．2Q T M 格网剖分的改进 为了解决上述问题，本文对球面三角形的细化 方法进行改进，以球面八分体的一个单元为例 如 图2 a 三角形的左右两边不变，还是为大圆距离， 而底边则是用A B 之间的纬线代替A B 之间的大 圆距离． 万方数据 4 4 0中国矿业大学学报第3 4 卷 囝岔岔 ‘a b c 图2 三角形底边的修正 F i g ．2 M o d i f i c a t i o no fb o t t o ms i d eo ft r i a n g u l a rg r i d 改进后的Q T M 三角剖分在不同程度上解决 了传统Q T M 剖分存在的两个问题 1 格网的变形减小从首次细化可以看出，中 间大三角形的面积略微减小，底边三角形的面积略 微增加．这样随着层次的递归细化，变形积累的速 度相对较小． 2 格网与地理坐标之间建立对应关系从首 次细化可以看出 如图2 ，上三角形的底边与纬度 线是符合的，这个特征使其可以直接确定球面上的 一个点在哪一个球面三角形上，即很容易与球面经 纬度格网坐标进行转化． 3Q T M 格网的几何变形计算 设A ，B ，C 为球面上任意三点，X 。，X 。，X 。分 别为A ，B ，C 三点的向量，则球面三角形A B C 的曲 面面积S 和A B 顶点之间的大弧距离D 舳为 S ，一R 2 『_ ∑嘶一玎] ， 1 。鬲 。 其中啦 a r c c o s [ 蔫鹁蔫蔫] ， i 1 ，2 ，3 ；X o X 3 ；X 4 X 1 ， D A 且一尺口 R a r c c o s X 1 X 2 ， 2 这里球面三角形的三条边都是大圆弧线．但是 在上述改进的Q T M 格网中，每个三角格网的底边 都是纬线，不能直接应用上述公式，现把三角形的 底边“纬线”A B 按经度平分为咒段 如图3 1 纬线A B 的长度可用雄段大圆弧段口『口『 1 代替歹 0 ，1 ，2 ，⋯，行一1 ；其中口o A ，口。 B ；每段 大圆弧段a j a 川的距离可按公式 1 近似计算出； 2 球面三角形△A B C 就分为咒个小三角形 口f C a s 1 歹 0 ，1 ，2 ，⋯，n 一1 I 其中口o A ，‰ B ， 每个小三角形的面积可按公式 1 近似计算出； 3 纬线A B 的长度精度和球面三角形△A B C 的精度可用n 值进行控制． 图3 三角形底边的近似计算 F i g ．3A p p r o x i m a t ec o m p u t a t i o no f b o t t o ms i d eo ft r i a n g u l a r 这样三角形曲面面积S ，和A B 之间的“纬线” 距离D B 的计算公式为 H ln 一13 S ， ∑S 勺q ，一∑尺2 [ ∑o t i 一丌] ， 3 J 0J 0 1 1 1 其中瓯一A ，‰一B n - - 1 “ 一1 D 邶 ∑R A O ∑R a r c c o s X 矿X a j 1 ． 4 j oJ 0 5 变形实验分析 利用公式 3 和 4 ，作者针对球面一个八分单 元 其他7 个单元一样 ，共计算了1 6 层次的球面三 角形的面积及长度，给出了三角形面积变形的分布 区段 如表1 及其最大／最小面积和最大／最小边 长的比值变化 如表2 ． 裹1三角形面积变形的分布区段 T a b l e1D i s t r i b u t i o ns e c t i o n so fd i s t o r t i o ni nt r i a n g u l a ra r e a s 万方数据 第4 期赵学胜等基于Q T M 的全球离散格网变形分布及收敛分析4 4 1 5 ．1各层次变形分布规律 根据表1 中的计算数据，我们给出了第2 ，4 ， 6 ，8 ，1 0 ，1 2 六个剖分层次的三角形格网变形分布 图 如图4 所示 ，可以看出随着剖分层次的增加， 搽 七 陕 援 l O 垒8 赢6 叁 糈 0 ．4 0 ．3 0 ．2 0 - 1 051 52 53 5 分段区域／％ a 分段区域／％ d 格 士 碘 援 色鬈 1 0 茎。8 帮4 0 其三角形格网变形分布图越来越趋于稳定，接近于 正态分布；变形率的边界为[ 一2 5 ％，4 0 ％] ，而变形 率在一2 5 ％～2 5 ％之间的三角形数目占全部三角 形的9 9 ．9 9 8 ％． 分段区域／％ b 4 0 ．3 0 ．2 0 - 1 051 52 5 3 5 分段区域／％ e 6 0 0 5 0 0 籁4 0 0 塞3 0 0 醒 0 乞 ≤ 籁 七 碘 援 ⋯ 2 5 2 0 1 5 l O 5 O 分段区域／％ ．4 0 ．3 0．2 0 ．1 051 52 53 5 分段区域／％ f 图4 不同层次的变形分布特征 F i g 。4 D i s t r i b u t i o nc h a r a c t e r so fd i s t o r t i o ni nd i f f e r e n tl e v e l s 5 ．2Q T M 层次格网的收敛分析 从表2 中发现1 应用纬线代替大圆弧线进 行层次细化，减小了三角形格网的变形量 如图 5 a 1 2 随着格网的不断细化，三角形的最大和最 小面积的比值与最大和最小边长的比值越来越大， 但是其变化速度越来越小，最终收敛到1 ．7 3 和 1 ．8 6 左右，都不超过1 ．9 如图5 b ．这个特点使其 在递归剖分中，保持近似均匀的特征，有利于球面 实体的层次索引与扩展操作． 万方数据 4 4 2 中国矿业大学学报 第3 4 卷 j 霉 曾 6 结论 荆分层次 a 越 丑 剖分层次 b 图5 ．s ⋯／S 一和L ⋯／L 一随剖分层次的收敛特征 F i g ．5 C o n v e r g e n tc h a r a c t e r so fS ⋯／s 。i na n dL ⋯／L 。i nb yp a r t i t i o nl e v e l si n c r e a s i n g Q T M 是一种基于球面的可以无限细分地球 体拟合格网，它具有层次性和全球连续性特征，已 成为国际G I S 学术界一个新的研究热点．本文首 先修正了传统的球面Q T M 层次剖分方法，重点分 析了其格网几何特征的变异性分布规律和收敛性 阈值，通过实验计算得出以下结论 1 应用纬线代替大圆弧线进行层次细化，减 小了三角形格网的变形量． 2 随着剖分层次的增加，其三角形格网变形 分布图越来越趋于稳定，接近于正态分布；变形率 在一2 5 ％ 2 5 ％之间的三角形占全部三角形的 9 9 ．9 9 8 ％． 3 随着格网的不断细化，三角形的最大和最 小面积的比值与最大和最小边长的比值越来越大， 但是其变化速度越来越小，最终收敛到1 ．7 3 和 1 ．8 6 左右，均不超过1 ．9 ． 上述结果表明Q T M 格网在其递归剖分中， 保持了近似均匀的特征，有利于球面实体的层次索 引与扩展操作；且其变形阈值的存在，为全球离散 格网计算的精度分析和误差控制提供了基础．为了 提高数据精度和应用范围，下一步需要研究基于椭 球面的Q T M 剖分方法及变形分析． 参考文献 [ 1 ] D u t t o nG ．S c a l e ，s i n u o s i t y ，a n dp o i n ts e l e c t i o ni n d i g i t a ll i n eg e n e r a l i z a t i o n [ J ] ．C a r t o g r a p h y a n d G e o g r a p h i cI n f o r m a t i o nS c i e n c e ，19 9 9 ，2 6 1 3 3 5 3 ． [ 2 ] G o l dCM ，M o s t a f a v iM ．T o w a r d st h eG l o b a lG I S [ J ] ．I S P R SJ o u r n a lo fP h o t o g r a m m e t r ya n dR e m o t e S e n s i n g ，2 0 0 0 ，5 5 3 1 5 0 1 6 3 ． [ 3 ] 李德仁，朱欣焰，龚健雅．从数字地图到空间信息格网 [ J ] ．武汉大学学报 信息科学版 ，2 0 0 3 ，2 8 6 6 4 2 6 5 0 ． L iDR ，Z h uXY ，G o n gJY ．F r o md i g i t a lm a pt o s p a t i a l i n f o r m a t i o n g r i d [ J ] ．J o u r n a l o fW u h a n U n i v e r s i t y E d i t i o no fI n f o r m a t i o nS c i e n c e ，2 0 0 3 ，2 8 6 , 6 4 2 6 5 0 ． [ 4 ] D u t t o nG ．E n c o d i n ga n dh a n d l i n gg e o s p a t i a ld a t aw i t h h i e r a r c h i c a lt r i a n g u l a rm e s h e s [ A ] ．I n K r a a kMJ ， M o l e n a a rM E d ． 。P r o c e e d i n go f7 t hI n t e r n a t i o n a l S y m p o s i u m o n S p a t i a l D a t aH a n d l i n g [ C ] ． N e t h e r l a n d s 。1 9 9 6 ．3 4 4 3 ． [ 5 ] W h i t eD ，K i m m e r l i n gA ．C o m p a r i n ga r e aa n ds h a p e d i s t o r t i o no np o l y h e d r a lb a s e dr e c u r s i v et e s s e l l a t i o n so f t h es p h e r e [ J ] ．I n t e r n a t i o n a lJ o u r n a lo fG e o g r a p h i c a l I n f o r m a t i o nS c i e n c e ，1 9 9 8 ，1 2 8 8 0 5 8 2 7 ． ‘ [ 6 ] G o o d c h i l dM ，Y a n gSR ．Ah i e r a r c h i c a ld a t as t r u c - t u r ef o rg l o b a lg e o g r a p h i ci n f o r m a t i o ns y s t e m s [ J ] ． C V G I P ，1 9 9 2 ，5 4 1 3 1 4 4 ． [ 7 3B a r t h o l d i JI I I ，G o l d s m a nP ．C o n t i n u o u si n d e x i n go f h i e r a r c h i c a ls u b d i v i s i o n so ft h eg l o b e 口] ．I n t ．J ． G e o g r a p h i c a l 、I n f o r m a t i o nS c i e n c e ，2 0 0 1 ，15 6 4 8 9 一 ．5 2 2 ． [ 8 ] L u g oJA ，C l a r k eKC ．I m p l e m e n t a t i o no ft r i a n g u 一 、l a t e dq u a d t r e e s e q u e n c i n gf o rag l o b a lr e l i e fd a t a s t r u c t u r e [ A ] ．P r o c e e d i n g so fA u t oC a r t o1 2 [ c ] ． C h a r l o t t e ，N C ，1 9 9 5 ．4 5 5 4 6 3 ． [ 9 ] F e k e t eG ．R e n d e r i n ga n dm a n a g i n gs p h e r i c a ld a t a w i t h s p h e r eq u a d t r e e [ A ] ．P r o c e e d i n g s o f V i s u a l i z a t i o n ’9 0 [ C ] ．I E E EC o m p u t e rS o c i e t y ，L o s A l a m i t o s ，C A ，1 9 9 0 ．1 7 6 1 8 6 ． [ 1o ] L e eM ，S a m e tH ．N a v i g a t i n gt h r o u g ht r i a n g l em e s 一 ．h e si m p l e m e n t e da sl i n e a rq u a d t r e e [ J ] ．A C M t r a n s a c t i o n so nG r a p h i c s ，2 0 0 0 ，1 9 2 7 9 - 1 2 1 ． [ 1 1 ] S a h fK ，W h i t eD ，K i m m e r l i n gA ．G e o d e s i cd i s c r e t e g l o b a lg r i ds y s t e m s [ J ] ．C a r t o g r a p h ya n dG e o g r a p h i c I n f o r m a t i o nS c i e n c e ，2 0 0 3 ，3 0 2 1 2 1 1 3 4 ． [ 1 2 ] W h i t eD ，K i m m e r i n gJ ，O v e r t o nW ．C a r t o g r a p h i c a n dg e o m e t r i cc o m p o n e n t so fag l o b a ls a m p l i n g d e s i g nf o re n v i r o n m e n tm o n i t o r i n g [ J ] ．C a ．G I S 。 1 9 9 2 ，1 9 1 5 2 2 ． 责任编辑李成俊 万方数据