一种基于格网的快速等值线充填算法

发信人: courieryboo (小凡·每天灌水多一些...), 信区: DigitalWorld        
标  题: 一种基于格网的快速等值线充填算法
发信站: BBS 水木清华站 (Sun May 21 14:08:29 2000)

　　摘　要:本文提出一种基于格网的等值线跟踪，适用于任意边界分割的快速充填算法
，实现充填的矢量化效果。根据边界线与非封闭等值线间的关系，建立等值线间的拓扑
关系，并以树结构方式存储，以准确快速地实现边界线、非封闭等值线之间的封闭和封
闭等值线间的嵌套。该算法已成功应用于海量多波束地形数据的成图，克服了常用多波
束后处理成图软件栅格充填与等值线之间的失配。
　　关键词：网格数据；等值线跟踪；拓扑结构；填色
A Fast Algorithm of Color Fill between Contours
Based on Grid Data
WU Zi-yin, GAO Jin-yao
(Key Lab of Submarine GeoSciences,SOA,Hangzhou， Zhejiang,310012)
Abstract:Based on contour tracing for grid data,a fast algorithm of color fi
ll is proposed to cope with random boundaries surrounding data gaps and to r
ealize the vector effect of color fill graph. From the relationship between  
boundary lines and unclosed contours,the topologic structure among contours  
can be built and stored in a tree structure.Such a topologic structure displ
ays the linking and closing between boundary lines and unclosed contours,the
 nesting among closed polygon in the order of tree rings.It is successfully  
applied in mapping of huge volume of submarine topographic data observed by  
multibeam,and it overcomes the inconsistency between color blocks and contou
rs produced by mapping software for multibeam postprocessing.
Key words:grid data;contour tracing;topologic structure;color fill
1　引　言
　　 等值线充填，就其实质，是等值线间建立拓扑关系［1～3］，也就是建立一种树结
构关系，一直是一个比较棘手的问题。尤其在不规则内外边界，任意等值间距的情况下
，很难建立等值线间拓扑关系。在实际应用过程中，笔者发现有很多软件不能很好解决
这个问题，例如：GMT,SeaView,Simard,Elac等。本文将阐述在规则格网情况下，在边界
线的基础上，建立等值线间拓扑关系，最终实现任意边界，任意等值间距情况下的等值
线充填。
2　算法基本原理
　　 等值线跟踪是在已知格网点的基础上，内插出等值线点，然后跟踪等值点，形成封
闭或非封闭等值线［4～7］。非封闭等值线的端点必然落在边界线上，而边界线必然是
封闭的，通过跟踪边界线，再把非封闭等值线端点插入边界线，通过边界线建立等值线
间的拓扑关系，在此基础上跟踪出封闭多边形，实现等值线的填充。该算法分为以下几
大步骤：边界线的跟踪，非封闭等值线端点插入边界线中并排序，非封闭等值线建立拓
扑关系，跟踪封闭多边形并排序，等值线的充填。
2.1　边界线的跟踪
　　　要实现边界线的跟踪，首先要找出边界线点。所谓边界线点，就是在某一格网点
的周围至少有一空白格网点或非空的边框点，该点即为边界线点。然后用类似跟踪等值
线的方法即可跟踪出边界线（参见图1）。
图1　边界线跟踪
Fig.1　Tracing boundaries
　　笔者用三级链表来存储边界线。链表结构如下：
　　typedef struct BOUNDARYS //边界线数目链表
{
BOUNDARY ??pBoundary;//
某条边界线指针
BOUNDARYS?*p_Next;// 下一条边界线数目链表指针
BOUNDARYS（）
　　｛
　　pBoundary＝NULL;
　　p_Next=NULL;
　　　｝
} BOUNDARYS;
　　typedef struct BOUNDARY//边界线链表
{
BOUNDARYPOINT?*pPoint;//某一边界线点指针
BOUNDARY?*p_Next;// 下一边界线点指针
BOUNDARY()
　　{
　　pPoint=NULL;
　　p_Next=NULL;
　　}
} BOUNDARY;
　　typedef struct BOUNDARYPOINT//边界线点链表
{
CONTOUR?*pContour;//某条等值线指针
bool　Direction;// 等值线方向
BOUNDARY?*p_Next;// 下一边界线点指针
BOUNDARYPOINT()
　　{
　　pContour=NULL;
　　p_Next=NULL;
　　}
} BOUNDARYPOINT;
　　3个链表的关系是: BOUNDARYS→BOUNDARY→BOUNDARYPOINT; BOUNDARYS链表存储所
有的边界线, BOUNDARY链表存储某一条边界线, BOUNDARYPOINT链表存储非封闭等值线端
点。
2.2　非封闭等值线端点插入边界线中并排序
　　　 非封闭等值线端点必然落在边界线上，并且是有序排列的，在两个边界线点之间
的等值线端点按等值线值要么从高到低排列，要么从低到高排列（参见图2）。
图2　非封闭等值线与边界线关系
Fig.2　Relationship between unclosed contours and boundaries
　　笔者把非封闭等值线端点有序地插入BOUNDARYPOINT（边界线点链表）链表中。
2.3　非封闭等值线建立拓扑关系
　　在非封闭等值线端点插入边界线的基础上，非封闭等值线建立拓扑关系。
　　为了建立非封闭等值线拓扑关系，必须先建立这样一个等值线树结构：
　　typedef struct CONTOUR//某条等值线链表
　　　　{
　　　　float　Height;//等值线值
　　　　double　*X,?*Y;// 等值点坐标值
　　　　long　Num;// 等值线上的坐标点数目
　　　　CONTOURLABEL ?*pLabel;//等值线标注值链表指针
　　　　RECT　　ExtRc;//该等值线的最小扩展框;
　　　　bool　Closed;//等值线是否封闭标识符；
　　　　CONTOUR
　　　　　　*pHeadUp,?*pHeadDown,
?*pTrailUp,
　　　　*pTrailDown;//与该等值线有拓扑关系的等值线指针
　　　　bool
　　　　　　HUp,HDown,TUp,TDown;//标识等值线的方向
　　CONTOUR()
　　　　{
　　　　Height=-1;
　　　　X=Y=NULL;
　　　　Num=-1;
　　　　pLabel=NULL;
　　　　Closed=false;
　　　　p_Next=pHeadUp=pHeadDown=pTrailUp=pTrailDown=NULL;
　　　　HUp=HDown=TUp=TDown=true;
　　　　}
　　HEIGHTLIST　*p_Next;//下一等值线指针
　　CONTOURS　*p_NextContour;// 下一级等值线指针
　　}CONTOUR;
　　与某条非封闭等值线有拓扑关系的等值线最多有4条，即两端点各指向两条等值线，
这些等值线也可能指向它本身。（图3的填色效果表明该拓扑关系的可靠性）
图3　非封闭等值线与边界线建立拓扑关系
Fig.3　Topologic relation between unclosed
contours and boundaries
　　在“非封闭等值线端点插入边界线中并排序”中已阐述如何把等值线端点插入边界
线中，通过链表BOUNDARYPOINT（边界线点链表），很容易找到与等值线有拓扑关系的等
值线，并把它的指针写入链表CONTOUR（等值线链表）中。
2.4　跟踪封闭多边形并排序
　　 从某一条非封闭等值线出发，沿顺时针或逆时针方向跟踪，必然会返回到这条等值
线， 从而构成封闭多边形，然后把这些封闭多边形按扩展框的大小有序地排列，形成封
闭多边形嵌套系列，即完成封闭区域的跟踪。对于封闭等值线，可做为一封闭区域，在
跟踪好封闭多边形后，一起排序，并加入封闭多边形嵌套链表（图4表明该算法完全可以
建立复杂的拓扑、嵌套关系）。
图4　建立等值树并实现充填算法
Fig.4　Tree structure of contours built for realizing fill algorithm
为了储存跟踪的封闭多边形，笔者建立了一三重链表结构：
　　typedef struct BLOCKNUM//填充区域系列链表
　　　　{
　　　　BLOCKS　*pBlocks;//某一填充区域系列指针
　　　　BLOCKNUM*p_Next;//下一填充区域系列链表
　　　　BLOCKS()
　　　　　　{
　　　　　　pBlocks=NULL;
　　　　　　p_Next=NULL;
　　　　　　}
　　　　} BLOCKNUM；
　　typedef struct BLOCKS//填充区域系列链表
　　　　{
　　　　BLOCK　*pBlock;//某一填充区域指针
　　　　BLOCKS　*p_Next;//下一填充区域系列链表
　　　　BLOCKS()
　　　　　　{
　　　　　　pBlock=NULL;
　　　　　　p_Next=NULL;
　　　　　　}
　　　　}
　　typedef struct BLOCK//填充区域链表
　　　　{
　　　　PEN　hPen;//笔型
　　　　BRUSH　hBrush;//填充图案
　　　　CONTOUR　*pContour;//等值线指针
　　　　bool　Direction;//等值线方向:true:正向；false:反向
　　　　BLOCK ()
　　　　　　{
　　　　　　pContour=NULL;
　　　　　　Direction=true;
　　　　　　}
　　　　};
　　以上3个链表的关系是：BLOCK→BLOCKS→BLOCKNUM; BLOCK链表用于存储某一封闭多
边形，BLOCKS链表用于存储某一地形单元的封闭多边形系列（例如：海山，凹地），BL
OCKNUM链表用于存储BLOCKS。
2.5　等值线的充填
　　在“跟踪封闭多边形并排序”中已详细阐述如何从非封闭等值线跟踪出封闭多边形
，并储存在BLOCK（填充区域链表）链表中，同时根据BLOCK链表中CONTOUR（等值线链表
）链表中等值线值，设置封闭多边形的笔型（PEN）、填充图案（BRUSH）、颜色。建立
了非封闭等值线间的拓扑关系（储存在BLOCK中），同时建立了封闭多边形的嵌套关系（
储存在BLOCKS中）,再根据笔型、填充图案、颜色，很容易实现等值线的充填。
3　和其他算法的比较
　　有很多软件用栅格填充等值线，即在格网的基础上，把格网再细分成若干小格网，
再按格网的值，以矩形色块的方式实现等值线的填充［8～10］，例如：GMT, Simard多
波束系统，Elac多波束系统，SeaView等。这种算法比较简单、快捷，但有它本身的缺陷
，只适合小比例尺，格网很密的情况下，在大比例尺，格网稀的情况下会出现锯齿状多
边形边界（参见图5）。而本算法在任意比例尺，任意格网情况下都可非常好的实现等值
线的充填。
图5　锯齿状多边形边界
Fig.5　Zigzag polygon boundaries
　　“Win Surfer”是微机上应用很普遍的一种绘图软件，功能强大，速度快捷；笔者
把该算法的计算速度与“Win Surfer”软件对比了一下，速度不亚于“Win Surfer”软
件。笔者发现，在格网很密，图面变化很复杂的情况下，“Win Surfer”软件充填算法
会出现一些问题（参见图6），而本算法适合于任意情况（参见图7）。
图6　“WinSurfer”不能实现充填的范例
Fig.6　Graphics produced by “WinSurfer” failed in color fill
图7　本算法实现的充填图
Fig.7　Map of color fill realized by the fill algorithm proposed in this pap
er
4　算法的优点及应用前景
4.1　设计思路新颖、速度快捷
　　 该算法找到了一种快速建立等值树方法。本算法找到了等值线与边界线间的关系，
通过这种关系，很容易，同时也是很快捷的建立等值线间的拓扑关系。该算法不存在理
论上的缺陷，同时速度不亚于同类商用软件。
4.2　适用任意情况
　　在图面变化复杂，格网密，内外边界多的情况下，有很多软件无法进行等值线充填
，或者不能很好地进行充填，而本算法适用于任意情况。
4.3　应用前景广阔
　　 本算法不但很好地解决了等值线充填问题，而且在GIS应用上有很广阔的应用前景
。该算法准确、快速建立不同等值区域间的拓扑关系，可应用于精确统计特定区域的周
长、面积、体积等。
　　该算法也可适用于三角网情况下的等值线充填。该算法是在“863”计划海洋领域有
关多波束地形探测技术开发中研制的，它的应用也体现了我们自主开发的多波束后处理
成图软件的特色。
致谢　 以上研究是“863”计划海洋领域“820-01-01”课题的研究成果之一。参与该课
题的各位同仁给予了各种帮助，特别感谢金翔龙院士在课题研究过程中给予的具体指导
，也感谢“126”专项课题的同仁在算法应用、检验中给予的方便。
863计划海洋领域820-01-01课题资助。
作者简介：吴自银，男，28岁，助理研究员。主要从事多波束后处理软件编制GIS研究工
作。
作者单位：国家海洋局海底科学重点实验室,浙江杭州,310012
参考文献：
［1］　王伟，等. GeoStar中图形编辑与拓扑关系的建立［J］. 武汉测绘科技大学学报
， 1995，20(5).
［2］　袁修孝，龚健雅. 顾及地形特征线的数字高程模型软件包［J］. 武汉测绘科技
大学学报，1995，20(5).
［3］　孙玉国. 拓扑空间关系描述与2DT-String空间关系表达［D］.武汉：武汉测绘科
技大学，1993.
［4］　龚健雅. 顾及地形特征的DEM内插与等高线绘图子系统［J］. 测绘学报，1990，
15(1).
［5］　龚健雅. 关于DEM中多面函数内插法几个问题的研究［J］. 测绘通报，1995(5)
.
［6］　龚健雅,苏向辰. 一种快速内插数字地面模型的方法［J］.测绘通报，1987(2).

［7］　龚健雅. GIS中矢量栅格一体化数据结构与面向目标数据模型的研究［D］.武汉
：武汉测绘科技大学，1992.
［8］　毋河海. 地图数据库系统［M］. 北京：测绘出版社，1991.
［9］　李德仁，龚健雅，边馥苓. 地理信息系统导论［M］. 北京：测绘出版社,1993.

［10］　龚健雅. 整体SIS的数据组织与处理方法［M］. 武汉：武汉测绘科技大学出版
社，1993.　

很好

ok!

look

good

网格的数据在实际采集时是不容易得到的，有没有不规则TIN的更好的算法啊？最好是可以区分地性线的算法

不错不错<img src="images/post/smile/dvbbs/em01.gif" />

<P>不错</P>

佩服，果然高手

good!