矢量数据向栅格数据转换的一种改进算法

1、收稿日期:!""#$"%$&#;修订日期:!""#$&"$"基金项目:国家自然科学基金项目(""&"*矢量数据向栅格数据转换的一种改进算法王建,杜道生(武汉大学测绘遥感信息工程国家重点实验室,湖北武汉(#""+摘要:地理信息系统的发展与空间数据结构的优化密不可分,栅格数据与矢量数据之间的高效转换是,-.的关键技术之一。由于栅格数据十分有利于空间分析中的叠置分析,因而通常需要将矢量数据转换成栅格数据。该文分析对比了地理信息系统的两种基本数据结构,在总结已

2、往矢量数据转换为栅格数据方法的基础上,依据边界代数多边形填充算法的基本原理,结合绘图作业时采用的正负法,提出了一种改进的折线边界(数据串跟踪方法。该算法原理简单,不需进行复杂的距离比较运算,运算速度快,并且通过简单的角度判断保证了填充的精度。关键词:矢量数据;栅格数据;边界代数中图分类号:/!"文献标识码:0文章编号:&*!$"%"(!""("&$""#&$"("引言地理信息系统(,-.是以空间数据为基础,采用地理模型分析方法,适时提供多种空间的和动态的地理信息,为地理研

3、究和地理决策服务的计算机服务系统&。空间数据通常有矢量数据(1234567848和栅格数据(98:4267848两种形式。栅格数据结构又称为网格数据结构(;6<=32>>,是将平面划分为?A 个正方形小方格,每个小方格用(B ,C坐标标识,即自然地理实体的位置和形状用它们所占据的栅格行列号来定义,栅格数据模型对地图数据的类型和属性可以用每个栅格的属性值表示,其最明显的特点是属性明显,定位隐含。矢量数据结构是通过记录坐标的方式,表示点、线、多边形等地理实体,自然地理实体的位置是用其在坐标参考系中的空间位置来定义的,坐标空间设为连续,其特点是定位明显,属性隐含。作为两种不

4、同的数据结构,矢量结构和栅格结构之间有很大的不同,二者各有优缺点!,#(表&。目前,由于,-.数据格式不尽相同,而一种,-.软件所接受的数据格式是一定的,为了便捷而高效地实现数据的传输和交换,必须采用一定的规则对不同数据源的数据进行转化。在当今数字化时代,越来越需要运用,-.进行空间数据的分析。在空间分析时,由于栅格形式的,-.数据非常适合诸如多边形叠加、空间相关、平均值计算和空间模拟等空间分析,因而通常需要把矢量数据转换成栅格数据。点和线的栅格化方法目前讨论得已经比较成熟,方法也趋于固定。对于点状实体,每个实体仅由一表&栅格、矢量两种数据结构的比较!"#$%&

5、;&("*+,-#%./%-*",.%*,.*01.0*%"-23%1.*,.*01.0*%比较内容栅格矢量数据结构不严密且简单严密而复杂数据存储量大小空间位置精度低高图形运算处理算法较容易,便于叠加及多要素综合分析算法较复杂,特别是多边形叠置处理输出表示不美观但便宜,难以表达线状、网格状的事物图形显示质量好且昂贵,对线状、网格状事物分析方便拓扑与网络分析容易困难并行处理容易实现难以实现投影变换实施过程采用逆变换的方法,即从变换后的图像寻找出目标图与原图之间的对应关系点数相同,一一对应,可直接利用相关公式进行变换适合图像色彩、阴影或形状变化复杂的图像线形图

6、像、阴影和色彩简单的图像表达空间变换能力强差个坐标对表示,其矢量数据向栅格数据的转换基本上是坐标转换精度的问题。线实体和面实体的边界可用数据串(用折线逼近、弧段(由数学函数定义或由它们的连接来表示它们的位置和形状。在矢量结构中,数据串是由一系列坐标对表示,在将其转换为栅格结构时,除把序列点的坐标对转换为栅格的行、列坐标外,还需要根据栅格精度要求,在坐标点之间插满一系列栅格点,这个也可以通过两点的直线方程得到(。目前,线段的栅格化有两种常用方法:770法(数字微分分析法和D 62:2A E 8?法。D 62:2AE 8?算法不仅速度快、效果好,而且可以在理论上证明它是目前同类各种算法中最优的%。

7、&面(多边形的栅格化方法面的栅格化方法又称为多边形填充,即在矢量表示的多边形边界内部的所有栅格上赋予相应的多第!"卷第&期!""(年&月地理与地理信息科学,25;68F E C8A =,25$-A G 56?84<5A .3<2A 3215>H !"I 5H &J 8A K 86C!""(边形编号(属性,从而形成栅格数据阵列。!"!面(多边形栅格化的传统方法矢量数据向栅格数据的转换属于#$%中比较经典的问题,积累了很多方法,如内部点扩散法、复数积分法、射线法等,它们各具特点(

8、表&(。表&多边形矢量化传统方法的原理和特点!"#$%&!&%(*+$%,"*-+&"("+.%(,.+,/0.&%.("-./*"$/$12/*3%+./(4"./*5%.&/-,传统方法基本原理特点内部点扩散法由多边形一个内部点(种子点开始,向其个或*个方向的邻域扩散。判断新加入的点是否在多边形边界上,如果是,不作为种子点;否则当作新的种子点与原有种子点一起进行新的扩散运算,直到区域填满、无种子点为止。算法复杂,需要在栅格阵列中进行搜索,占内存较大;当复杂图形的同一

9、多边形的两条边界落在同一个或相邻的两栅格内时,会造成阻塞,进而造成扩散不能完成;若多边形不完全闭合时,会扩散出去。复数积分法对全部的栅格阵列逐个栅格单元判断栅格归属的多边形编码,即由待判断点对每个多边形的封闭边界计算复数积分,如果积分值为&!+,则该待判断点属于此多边形。设计简单,可靠性较好;涉及许多乘除运算,运算时间长,难以在低档计算机上采用。射线算法由待判断点向图外某点引射线,判断该射线与某多边形所有边界相交的总次数,如果相交偶数次,则待判点在该多边形的外部;如果为奇数次,则待判点在该多边形内部。要逐点判别栅格点在某多边形之外或之内;要计算与多边形的交点,计算量大;当射线与多边形相

10、交的某些特殊情况(如射线通过多边形某个顶点时,会影响交点个数,需特殊处理,增加了编程的复杂性。扫描法该算法是对射线算法的改进。具体方法是,按扫描线的顺序,计算多边形与扫描线的相交区间,再用相应的属性值填充这些区间。省略了计算射线与多边形交点的大量运算,提高了效率;要预留一个较大的数组来存边界点;当射线与多边形相交的某些特殊情况(如射线通过多边形某个顶点时,会影响交点个数,需特殊处理,增加了编程的复杂性。边填充算法对每条扫描线和多边形每条边上的交点,将该扫描线上交点右方的所有像素取原属性值之补,多边形方向任意。算法简单;对于复杂图形,每一像素可能被访问多次,增加了运算量;为减少边填充算法访问像素

11、的次数,可引入栅栏。!"&面(多边形栅格化的新方法随着计算机技术的发展,对于该问题又提出了许多新的方法。!黄波和陈勇提出颜色填充法,其基本原理是根据每个多边形编码,给该多边形赋一个颜色,并用该颜色填充此多边形。然后判断每个栅格中心点的颜色值(许多高级语言均提供此功能,由颜色值即可求出相应的多边形编码。该算法不用求交点,因而速度较快,尤其当多边形的边界所包含的弧段数较多并较为复杂时,更显示其优越性。&李志清提出“掩模”(-.%/法进行面状图的栅格化0。其原理类似于印制照片的方法,“掩模”的作用就像一张底片,“白”处的光透过,“黑”处被阻拦。这里的“掩模”实际上是一个单色

12、位图,即只有黑白两色,它与栅格阵列的大小相同,位置也一一对应。对于某一多边形,首先将二进制位图全置“1”(白,读入边界点的坐标值,以黑色(“!”填充此多边形,从而生成此多边形的单色位图。将位图与栅格阵列的像元进行逐个比较,当位图为黑色(“!”时,将栅格阵列中相应行列处的灰度值赋予多边形编号,从而完成一个多边形填充。该方法省略了填充算法的复杂编程过程,节省内存,大大提高了程序的运行效率。,任伏虎提出边界代数多边形填充算法(23456789.:;<=87>+:+5;,2.>,是目前使用和讨论较多的方法之一(,*。它基于积分算法,其基本思想是:对每幅地图的全部具有左右多边形编号的边

13、界弧段沿其前进的方向逐个搜索,当边界上行时,将边界线位置与左图框之间的网格点加上一个值:%?(左多边形编号(右多边形编号;当多边形下行时,将边界线位置与左图框的栅格加上一个值: ?(右多边形编号(左多边形编号,而不管边界线的排列顺序(图!。该方法的优点是它不是逐点搜索判别边界,而是根据边界的拓扑信息,用加减运算将拓扑信息动态地赋予每个栅格点,算法简单,可靠性好,每边仅计算一次,免去了公共边界重复运算,运算速度快, 同时少受内存容量的限制。卷期王建等:矢量数据向栅格数据转换的一种改进算法 移动;否则第一步沿!轴移动。将该原理应用到边界代数多边形填充算法中。在现实世界中面状地物可以定义为多个圈的集

14、合,圈为单个多边形,顺时针表示内部属于该面状地物,称为外圈,逆时针表示挖去的“洞”,称为内圈,有时也称圈为多边形。圈由弧段组成,弧段又由直线段组成,因此,在进行该算法时按照圈弧段直线段的层次循环跟踪。由此可以得到如下的过程(以直线段上行为例,下行同理可得:("边界跟踪,按多边形边界线弧段直线段的层次循环进行。"对每条直线段,读入两端点坐标值#(!#,$#,%(!%,$%;&按照点的栅格化方法计算两端点所在的栅格行列号,并计算#、%所在行、列数的增量,并取绝对值得!,$;(确定判别函数的初值:如果直线与!轴夹角在*+!"(+,之间,即!(!%!#/($%-$

15、#!"./+,0-./.",否则0.;*判断直线段的走向:若#0.,跟踪沿!轴方向,直线段所在的栅格列数发生变化,判别函数0-$。比较!%和!#的大小,如果!%$!#,点#在点%的右边,跟踪到的列数1减"否则跟踪到的列数1加"。若$.,跟踪沿$轴方向,直线段所在的栅格行发生变化,判别函数02!。由于是上移"行,所以行数加"。(&当跟踪到的行发生变化时,就对该行左边的栅格进行填充处理。在该行中,为跟踪到的列1与左图框之间的栅格赋上属性值:30(左多边形编号-(右多边形编号。(对于每条直线段都要循环!2$次,直至到达%点所在的栅格

16、为止,该条直线段才算跟踪完毕。转入下一条直线段的边界跟踪和栅格填充处理。(结语笔者对上述算法用45%编程进行了实验,对有&+(个点的&6个多边形进行栅格化。如果采用"+.78.的栅格对其进行多边形填充,只需要花费./.9:,如果采用(6.7&*.的栅格对其进行多边形填充,则需要使用./."6:。由此可见,该算法切实可行、程序可靠性良好、速度较快。改进的边界跟踪方法完全保留了边界代数多边形填充的基本优点,在沿边界线进行判断的同时也就完成了栅格填充,而且判别函数简单,只需进行简单的加减运算,无需距离的比较,保证了多边形栅格化的运算效率。另外,仅通过对直线

17、角度的判断,就可以容易地得出边界线第一步的走向,保证了多边形填充的精度。当然,该方法仅适合于用数据串表示的多边形,至于用弧段或用数据串和弧段的连接表示的多边形如何转换成栅格数据还需进一步研究。参考文献:"叶为民,张玉龙,朱合华,等;地理信息系统中的栅格结构与矢量结构1;同济大学学报(自然科学版,&.&,(.(":"."-".+;&王让会;浅议地理信息系统的组织管理及应用1;测绘通报,"886,*(+:6-".;(黄波,陈勇;矢量、栅格相互转换的新方法1;遥感技术与应用,"88+,"

18、.(:9"-9+;*龚健雅;地理信息系统基础<科学出版社,&.""9=-"98;+武汉大学资源与环境科学学院万象>?3研究室;空间数据的结构转换;A A B :&C D :;E A F :G ;D H F ;I J /K L C H D J /I M F C :D E L C D /KN :/I */".;A G ;&.(-.&-&.;9张超,陈丙咸,等;地理信息系统<北京:高等教育出版社,"88+;+9-9.;=李志清;O ?P >?3中的矢量数据向栅格数据的格式转换1

19、;林业资源管理,"88*(9:="-=(;6张超;地理信息系统实习教程<北京:高等教育出版社,&.;=.-=*;8吴华意,龚健雅,李德仁;无边界游程编码及其矢栅直接相互转换算法1;测绘学报,"886,&=(":9(-96;".徐庆荣,杜道生,黄伟,等;计算机地图制图原理<武汉:武汉测绘科技大学出版社,"88(;(9-(6;!"#$%&(*!+,&-./$0&1&2"30&&-",45.&.623.&72.2O #P

20、 >1N L J ,QL M -:D J K(!"#$%&$,(*+,+-./01-23,(*+456678,9-+*!83.&25.:R D H D S D T M B G D J A M U >?3N :I T M :D T V C D T L A D H A M A D M B A N G N W L A N M J M U :BL A N L T H L A L :A C F I A F C D ;R D D U U N I N D J A G F A F L T I M J S D C :N M J X D Y A E D D J S D I A

21、 M C L J H C L :A D C H L A L N :M J D M U A D Z D V A D I J M T M K N D :N J>?3;M C A D :L Z D M U A D I M J S D J N D J I D U M C M S D C T L V L J L T V:N :,A D S D I A M C H L A L L C D L T E L V :A C L J :U D C C D H A M C L :A D C H L A L ;R D :D A E M U F J H L G D J A L T H L A L :A C F I

22、 A F C D :M U >?3E D C D L J L T V W D H L J H I M G B L C D H L A A D X D K N J J N J KM U A N :B L B D C ;4L C N M F :I M J S D J A N M J L T L B B C M L I D :M U I M J S D C A N J K SD I A M C H L A L A M C L :A D C H L A LE D C D :FG G L C N W DH ,L J H A D J A D B L B D C B C D :D J A D H L

23、J N G B C M S D H X M F J H L C V -A C LI NJKL T KM CN A G ,E N I E L :X L :D H M J%#(%M F J H L C V #T K D X C LN T T N J K L J HM :N A N S D -P D K L A N S D L T KM C N A G U M C H C L E N J K K C L B :;R D B C N J I N B T D M U A N :L T K M C N A GN :N G B T D ,L :A D I M G B F A L A N M J L J H

24、I M G BL C N :M J M U H N :A L J I D X D A E D D J A E M B M N J A :N :J M A J D I D :L C V;R D C D U M C D ,N A I M J :N H D C L X T V N G B C M S D :A D :B D D H M U A D H L A L I M J S D C :N M J ,L J HG L N J A L N J :A D U N T T N J K B C D I N :N M J A C M F K L :N G Y B T D F H K G D J A M U

25、A D L J KT D L :E D T T ;9:;&*3:S D I A M C H L A L ;C L :A D C H L A L ;X M F J H L C V L T K D X C L 页*(第地理与地理信息科学第&.卷 矢量数据向栅格数据转换的一种改进算法作者:王建, 杜道生作者单位:武汉大学测绘遥感信息工程国家重点实验室,湖北,武汉,430079刊名: 地理与地理信息科学英文刊名:GEOGRAPHY AND GEO-INFORMATION SCIENCE年,卷(期:2004,20(1被引用次数:15次参考文献(10条2002(012.王让会浅议地理信息系

26、统的组织管理及应用期刊论文-测绘通报 1998(054.龚健雅地理信息系统基础 20015.武汉大学资源与环境科学学院万象GIS研究室空间数据的结构转换 20037.李志清WINGIS中的矢量数据向栅格数据的格式转换 1994(068.张超地理信息系统实习教程 2000相似文献(10条1.学位论文熊卫军矢量和栅格数据一体化及地理信息的SVG发布技术研究20032.学位论文孙虎网络环境下多源空间信息集成技术研究2006随着地理信息的应用日益广泛,大批地理信息系统的建立。越来越多的行业建立了具有自己行业特征的地理信息系统。近年来随着新技术不断出现,人们对地理信息系统和空间数据库的认识已经提高到系统级数据集成的高度,对不同系统之间空间数据的互操作要求越来越高。空间Web服务(