编码递归迭代

第41卷第4期2013年7月河海大学学报(自然科学版)JournalofHohaiUniversity(NaturalSciences)Vol.
41No.
4Jul.
2013DOI:10.
3876/j.
issn.
10001980.
2013.
04.
002摇摇收稿日期:20120712基金项目:国家"十一五冶科技支撑计划(2010BAC69B02);国家自然科学基金(50939006,51179203,51021006);国家重点基础研究发展计划(973计划)(2006CB403404)作者简介:刘佳嘉(1985—),男,江苏扬州人,博士研究生,主要从事水文水资源模型构建及应用研究.
E鄄mail:vaver@foxmail.
com通信作者:周祖昊,教授级高级工程师.
E鄄mail:zhzh@iwhr.
com基于DEM河网干支拓扑关系的子流域编码规则刘佳嘉,周祖昊,贾仰文,王摇浩(中国水利水电科学研究院流域水循环模拟与调控国家重点实验室,北京摇100038)摘要:为实现子流域划分、编码过程中多汇流编码并达到加密无分叉河段的要求,提出一种新型的子流域编码规则———干支拓扑编码规则.
它以河网干支流拓扑关系为基础,采用层次继承式编码规则,从流域出口逆流而上逐个对子流域进行编码.
该编码规则能确保上游子流域编码始终包含下游编码信息,从而实现上下游拓扑关系运算.
渭河流域应用实例表明,干支拓扑编码规则符合单向流不规则树状结构编码要求,能实现单枝结构、二叉结构以及多叉结构的拓扑编码.
关键词:干支流拓扑关系;干支拓扑编码规则;子流域编码;继承式编码规则;渭河流域中图分类号:TV212郾4摇摇摇文献标志码:A摇摇摇文章编号:10001980(2013)04028806Arulefordelineationandcodificationofsub鄄watershedsbasedonstem鄄branchtopologicalrelationshipofDEMdigitalrivernetworkLIUJiajia,ZHOUZuhao,JIAYangwen,WANGHao(StateKeyLaboratoryofSimulationandRegulationofWaterCycleinRiverBasin,ChinaInstituteofWaterResourcesandHydropowerResearch(IWHR),Beijing100038,China)Abstract:Anewruleforsub鄄watershedcodificationisputforwardtorealizesub鄄watersheddivisionandmulti鄄confluencecodificationandtosplitanon鄄bifurcatedriverintosmallparts.
Thisrule,whichiscalledstem鄄branchtopologicalcodification(SBTC),isdevelopedbasedonthestem鄄branchtopologicalrelationshipofdrainagenetworks.
TheSBTCcodesthedrainagenetworksfromtherivermouthtothesource,andusesthehierarchicalinheritanceruletoreflecttheupstreamanddownstreamtopologicalrelationship.
TheapplicationoftheruletotheWeiheBasinshowsthattheSBTCiscompetentforthecodingofanomaly鄄simulateddendriticdrainagenetworks,whichhaveone鄄way,two鄄way,andmulti鄄wayconfluencesituations.
Keywords:stem鄄branchtopologicalrelationship;stem鄄branchtopologicalcodification;sub鄄watershedcodification;inheritedcodificationrule;weiheBasin近年来基于子流域划分的分布式水文模型应用广泛,如SWAT模型[1鄄2]、WEP鄄L模型[3鄄4]等.
这类模型将研究流域划分成一系列子流域,分别对各子流域进行参数计算及水文模拟,从而实现大流域分布式模拟计算.
基于流域DEM模拟河网的子流域划分的一般步骤包括:(a)使用DEM提取模拟河网;(b)使用某种编码规则对模拟河网各个河段进行编码;(c)对所有流入相同河段的栅格区域赋值当前河段编码作为子流域编码[5鄄8].
因此,可以认为子流域编码方案即为河网编码方案.
国际通用的主要河网编码方法有爱尔兰测站编码、芬兰河流编码、美国Pfafstetter编码、德国LAWA编码等[6,9],但大部分编码方法均不适合子流域编码.
高效的子流域编码规则应具有以下特点:(a)每个编码对应一条河段,每个河段具有唯一编码;(b)编码能够反映河道间的拓扑关系,通过编码可以判别子流域之间的上下游关系;(c)能够通过编码直接计算相邻上下第4期刘佳嘉,等摇基于DEM河网干支拓扑关系的子流域编码规则游子流域编码,而非低效的遍历搜索.
基于上述特点,广泛采用的子流域编码方法主要有2种:Pfafstetter编码[5,10]和二叉树编码[11鄄13].
随着分布式水文模型的应用及发展,对子流域编码方法提出了更高的要求:(a)能够处理多河段汇入同一河段的情况,这种情况在农田灌溉及城市管网中很常见,而且基于DEM提取的河网也时常会出现;(b)能够加密无分叉河段,避免狭长子流域的出现;(c)能够考虑水库、水文站位置进行编码[14鄄16].
Pfafstetter编码和二叉树编码仅能部分满足上述要求,鉴于此,笔者结合Pfafstetter编码和二叉树编码的优点,提出一种全新的编码规则———干支拓扑编码规则.
1摇干支拓扑编码规则一般而言,河流都是一条干流加上若干支流的拓扑结构,而各支流同样具有自己的干流和次级支流.
干流、支流意义如下:就某级别河道而言(例如第n级河道),它本身所在的河道为干流,而直接流入该河道的第n+1级河道是其直接支流,流入其直接支流的是间接支流;同时第n级河道干流又是第n-1级河道的一条支流.
本文中支流是指直接支流,且河流级别数值小的为高级河流,数值大的为低级河流.
由于子流域划分同河网中各河段密切相关,河网编码均可理解为子流域编码.
1郾1摇一元干支拓扑码干支拓扑编码规则是一种基于干流河段的编码方案,能反映河网拓扑关系.
编码规则中,干流由最大集水面积确定.
确定干流后,所有流入干流的河流均认为是支流.
干流的支流汇入节点以及干流上的水文站、水库、排污口等要素将干流分割成若干段,称之为干流河段,每个干流河段内没有其他支流汇入.
分割完干流河段后,由当前干流出口逆流而上,对经过的每个干流河段依此编码为1,2,3……直到干流源头,称为干流码;每一级别干流河段都具有相应级别的干流码,都是从1开始编码.
干流码所使用的编码字符数由全流域所有河流最大干流分段数决定,1个字符能编码9个干流河段(1~9),2个字符能编码99个干流河段(1~99),依此类推,本文以2个字符干流码为例进行编码说明.
对于1级河流而言,其干支拓扑码就等于其本身级别的干流码.
对于其他级别的河流而言,编码规则为:汇入干流河段的干支拓扑码+支流标识码(简称支流码)+当前级别干流码.
支流码是当前级别河流相对于其汇入干流河段的支流序列编号,从1开始,依次增加(由于流入相同干流河段的支流数一般不超过9个,所以使用1个字符编码就能满足支流序号的编码需求,为了便于区分,笔者使用带下划线的数字表示支流码).
支流码的引入使干支拓扑码能够将多河段汇流作为一般情况进行处理.
如果某级别河流没有支流,则仍需给该河段编码,编码为1(前面补0以满足干流码字符数要求).
例如,图1中编码为03201101的河段没有支流,当前级别干流码为01(最右边2个字符);其直接汇入的河段为03201河段,它相对于03201河段的支流码为1.
图1摇干支拓扑码编码示意图Fig.
1摇Sketchmapofstem鄄branchtopologicalcodification干支拓扑码能清晰地反映河流拓扑关系,并对流域内每条河流进行唯一编码及定位.
一般而言,一元干支拓扑码具有"干流码鄄支流码鄄干流码鄄支流码鄄…鄄干流码冶的形式,即干流码、支流码交替出现,且编码最后2位(干流码字符数)一定是末级河道的干流码.
从编码结构可以看出,判别2个子流域是否具有上下游关系,只需要检测其中一个编码是否等于另一个编码左边若干连续字符,若等于,则是其下游河段.
一元干支拓扑码能实现对下游流入子流域编码的直接定位计算:(a)如果当前河段干流码大于1,则干流码减去1后即为流入河段编码;(b)如果干流码等于1,则直接消去最右边的干流码和支流码(图1实例中,消去右边3位字符即可,如03201汇入河段即为03河段).
干支拓扑码的编码结构相似度高,可以递归完成全流域河网编码,从而实现计算程序的自动编码处理.
982河海大学学报(自然科学版)第41卷1郾2摇多元干支拓扑码一元干支拓扑码与Pfafstetter编码很相似,编码规则简单、使用了继承式编码方式、每级别河段编码包含着高级别河段的编码信息,但其存在编码字符过多的问题.
如果每个级别干流码使用4个字符进行编码,则7级河流的一元干支拓扑码共需要31个字符,编码字符数量过多,而且编码字符利用率低(大部分是占位字符"0冶).
为解决上述问题,将一元干支拓扑码拓展成多元干支拓扑码,主要思路为:(a)拆分干支拓扑码为干流流程码、支流流程码.
(b)引入干流掩码以减少干流码占位字符.
干流流程码是指被编码河段汇入流域出口所流经的所有河段的干流码(包括自身干流码);支流流程码则包括所有流经河段的支流码;干流掩码则是每级别干流码所使用的字符数.
例如图1中03201101河段所对应的多元干支拓扑码为(111,311,121).
编码"111冶是干流掩码,表示当前河段为3级河流河段(由字符个数确定),每级干流码使用1个字符进行编码.
编码"311冶是干流流程码,根据干流掩码数值,每级别河流河段干流码分别为"3冶,"1冶,"1冶(消去了占位字符"0冶).
编码"121冶是支流流程码,其中右边"21冶来自原编码,最左边的"1冶表示整个流域主干流对流域出水口的支流标识,一般等于"1冶.
干流掩码、干流流程码、支流流程码均延续了继承式编码规则,靠左的字符表示下游流经河段的对应编码,靠右的字符表示上游河段对应编码.
干流掩码字符数为编码河段所在河流的级别数,而干流掩码各数字总和等于干流流程码编码字符数.
由于多元干支拓扑码完全拓展于一元干支拓扑码,所以能唯一标识流域中每一个河段,具有一元拓扑码的所有功能.
2摇干支拓扑编码规则的实例应用以渭河流域为例进行子流域划分及编码,来说明干支拓扑码对新编码要求的支持能力,其中DEM分辨率为1km.
根据多元干支拓扑码的编码规则,笔者编写了子流域划分程序以自动完成流域划分编码.
程序输入数据由Arcgis软件相应水文分析模块从流域DEM数据计算获得.
程序生成子流域编码属性文件(表1)和子流域划分图层(图2、图3)(受篇幅限制仅展示局部信息).
从子流域编码属性文件中可知,渭河流域总共被划分成1360个子流域,最小河流级别为7级,干流流程码最多编码字符数为9,平均干流流程码编码字符数为4郾35.
子流域索引号是唯一的,按自然数顺序排列,用以指示对应子流域.
表1摇程序计算生成的子流域编码属性Table1摇Outputattributetableofcodificationprogram子流域索引码流出子流域索引码流入子流域索引码1流入子流域索引码2流入子流域索引码3河流级别干流掩码干流流程码支流流程码左左左左左左左左左691700655690656222162712左左左左左左左左左6987006966970322116261122699700000322116261121700702691699698222162612左左左左左左左左左摇摇摇注:流出子流域索引码是指下游流出的邻接子流域编码;流入子流域索引码是指上游流入的邻接子流域编码;表中流域最多有3个子流域流入,具体子流域个数根据实际河网而定,程序可自动计算并相应增加或减少数量.
结合表1和图2,可以看出干支拓扑码能够有效表示多汇流子流域上下游拓扑关系.
例如,图2中编号为700的子流域有3个河段(子流域)汇入,分别为子流域691,698和699.
其中子流域700的编码为(22,1626,12)而子流域691的编码为(22,1627,12),二级干流码"27冶比子流域700的"26冶大1,表示同子流域700处于同一级别河流上,且属于上游.
子流域698和子流域699的编码分别为(221,16261,122)和(221,16261,121),两者均以子流域700对应编码开始,表示位于子流域700所在河段的上游支流上,且支流编号分别为"1冶和"2冶.
图3展示了干支拓扑码对子流域编码新要求的支持能力.
图3(a)(b)表明本文编码可以考虑水库、水文站位置进行子流域划分;图3(c)(d)表明本文编码能够对无分叉河段进行加密处理,分割山区平原区或避免狭长子流域的出现.
3摇讨摇摇论多河段汇流是模拟河网不可避免的河道汇流现象,而对无分叉狭长河道的加密和根据水文要素点(水092第4期刘佳嘉,等摇基于DEM河网干支拓扑关系的子流域编码规则图2摇多河段汇入情况Fig.
2摇Acaseofmulti鄄riverconfluence库、水文站)进行子流域分割又是近些年来水文应用的具体实践要求[16],使得流域编码规则所能处理的河网结构由理想的二叉树转变为不规则树状结构(多叉树或单枝结构).
一般而言,河网树状结构可以分为3种类型:单枝结构、二叉结构、多叉结构.
Pfafstetter编码仅能够处理单枝结构[5,14鄄15]和二叉结构[10],但对多叉结构无能为力.
二叉树编码对二叉结构处理效率高,但对单枝结构和多叉结构处理能力不强;虽然可以通过引入虚拟节点的概念应用于单枝结构和多叉结构[17],但会丧失计算快捷的优势.
干支拓扑码以河网树状结构为一般处理对象,能够有效处理单枝结构、二叉结构以及多叉结构.
从渭河流域划分实例可以看出,干支拓扑码能够很好地实现树状河网的子流域划分及编码过程,这是相对于Pfafstetter编码和二叉树编码而言图3摇子流域划分新功能实现示例Fig.
3摇Casesofanewfunctionofsub鄄watersheddivision其具有的最大优势.
流域编码规则应具有简洁易懂、无特殊要求、具有编码一致性等特性.
而Pfafstetter编码和二叉树编码均存在不同程度的特殊规定.
Pfafstetter编码要求取最大集水面积的4条支流参与河道干流编码;二叉树编码也存在特殊要求,例如为克服编码容量限制而引入分区编码,为支持多叉结构而引入虚拟节点等.
这些特殊的编码要求使得在整个流域河网发生改变时(如增加或减少河流、河网合并等),必须使用原始数据进行重新编码或更新相关属性表,从而使新编码符合编码规范.
相对而言,干支拓扑编码规则简单、编码一致性高,在仅知道子流域编码的情况(无原始数据)时也能方便、快捷地实现流域编码的增加、删除等操作.
干支拓扑码采用继承式编码方式,能反映被编码河段汇入流域出口所流经的所有河段信息.
如果A河192河海大学学报(自然科学版)第41卷段经过B河段汇入流域出口,则A河段编码必然以B河段编码开头;如果A河段编码以B河段编码开头,则A河段一定经过B河段汇入流域出口.
否则不存在联系.
因此,通过某河流出口干流河段编码就可以获取整个支流的表示规则.
一般而言,如果水文模型不关注任意2个子流域之间的上下游拓扑关系,而仅仅使用子流域进行河道汇流演算,则根据表1,使用子流域索引码即可达成目的,不需要引入干支拓扑码.
本文编码程序能够确保子流域索引编号越小则该子流域越靠近上游.
即对某子流域进行河道汇流演算时,其上游子流域肯定已经完成了对应的河道汇流演算,这样就避免了繁琐的递归迭代运算,提高模型运行速率.
4摇结摇摇语本文提出的干支拓扑编码规则是一种基于河流干支流拓扑关系的编码方案,能够较好地实现对不规则树状结构河网进行子流域划分及编码.
干支拓扑编码规则的主体是各级河流干流河段,辅之以支流标识,可实现不同树状河网编码,并能在编码上反映河流级别以及上下游拓扑关系.
干支拓扑编码采用继承式编码规则,从流域出水口开始逆流而上,逐河段、逐级别按河段汇流流程进行编码,且上游子流域编码始终包括其所流经的下游子流域编码.
干支拓扑编码规则结构简单易懂,便于计算机自动处理.
相对于已有的Pfafstetter编码以及二叉树编码,其具有相当大的优势.
目前干支拓扑编码规则主要适用于单向流河网,对于多向流河网需要进一步研究.
参考文献:[1]ARNOLDJG,SRINIVASANR,MUTTIAHRS,etal.
Largeareahydrologicmodelingandassessment.
part玉:modeldevelopment[J].
JournaloftheAmericanWaterResourcesAssociation,1998,34(1):73鄄89.
[2]SRINIVASANR,RAMANARAYANANTS,ARNOLDJG,etal.
Largeareahydrologicmodelingandassessment.
part域:modelapplication[J].
JournaloftheAmericanWaterResourcesAssociation,1998,34(1):91鄄101.
[3]JIAYangwen,WANGHao,ZHOUZuhao,etal.
DevelopmentoftheWEP鄄LdistributedhydrologicalmodelanddynamicassessmentofwaterresourcesintheYellowRiverBasin[J].
JournalofHydrology,2006,331(1/2/3/4):606鄄629.
[4]贾仰文,王浩,王建华,等.
黄河流域分布式水文模型开发和验证[J].
自然资源学报,2005,20(2):300鄄308.
(JIAYangwen,WANGHao,WANGJianhua,etal.
DevelopmentandverificationofadistributedhydrologicmodelfortheYellowRiverBasin[J].
JournalofNaturalResources,2005,20(2):300鄄308.
(inChinese))[5]罗翔宇,贾仰文,王建华,等.
基于DEM与实测河网的流域编码方法[J].
水科学进展,2006,17(2):259鄄264.
(LUOXiangyu,JIAYangwen,WANGJianhua,etal.
MethodfordelineationandcodificationofalargebasinbasedonDEMandsurveyedrivernetwork[J].
AdvancesinWaterScience,2006,17(2):259鄄264.
(inChinese))[6]于淼,陈雪莲.
基于DEM的河网河段编码方法[J].
人民长江,2009,40(24):36鄄38.
(YUMiao,CHENXuelian.
TherivercodificationbasedonDEMdrainagenetwork[J].
YangtzeRiver,2009,40(24):36鄄38.
(inChinese))[7]黄娟,申双和,殷剑敏.
基于DEM对江西潦河流域河网信息提取方法[J].
气象与减灾研究,2008,31(1):49鄄53.
(HUANGJuan,SHENShuanghe,YINJianmin.
DrainagenetworkextractioninLiaoheBasedonDEM[J].
MeteorologyandDisasterReductionResearch,2008,31(1):49鄄53.
(inChinese))[8]朱超,于瑞宏,刘慧颖,等.
基于DEM的乌梁素海东部流域河网信息提取[J].
水资源保护,2011,27(3):75鄄79.
(ZHUChao,YURuihong,LIUHuiying,etal.
InformationextractionofdrainagenetworkoftheeasternbasinofWuliangsuhaiLakebasedonDEM[J].
WaterResourcesProtection,2011,27(3):75鄄79.
(inChinese))[9]BRITTONP.
Rivercodingsystemsforriverbasinmanagementandreporting[M].
USA:EUGISWorkingGroupGuidanceDocument,2002.
[10]VERDINKL,VERDINJP.
AtopologicalsystemfordelineationandcodificationoftheEarth爷sriverbasins[J].
JournalofHydrology,1999,218:1鄄12.
[11]LITiejian,WANGGuangqian,CHENJi.
Amodifiedbinarytreecodificationofdrainagenetworkstosupportcomplexhydrologicalmodels[J].
Computers&Geosciences,2010,36(11):1427鄄1435.
[12]李铁键,王光谦,刘家宏.
数字流域模型的河网编码方法[J].
水科学进展,2006,17(5):658鄄664.
(LITiejian,WANGGuangqian,LIUJiahong.
Drainagenetworkcodificationmethodfordigitalwatershedmodel[J].
AdvancesinWaterScience,2006,17(5):658鄄664.
(inChinese))[13]邓利,李铁键,刘家宏,等.
数字流域河网编码方法应用实例[J].
泥沙研究,2007(3):68鄄72.
(DENGLi,LITiejian,LIUJiahong,etal.
Applicationofthedrainagenetworkcodificationmethodindigitalwatershedmodel[J].
JournalofSediment292第4期刘佳嘉,等摇基于DEM河网干支拓扑关系的子流域编码规则Research,2007(3):68鄄72.
(inChinese))[14]雷晓辉,王海潮,田雨,等.
南水北调中线受水区分布式水文模型子流域划分研究[J].
南水北调与水利科技,2009,7(3):10鄄13.
(LEIXiaohui,WANGHaichao,TIANYu,etal.
SubbasindelineationfortheserviceareasofSouth鄄to鄄Northwaterdiversionproject[J].
South鄄to鄄NorthWaterDiversionandWaterScience&Technology,2009,7(3):10鄄13.
(inChinese))[15]雷晓辉,田雨,白薇,等.
基于DEM的子流域划分方法改进与应用[J].
人民黄河,2011,33(2):32鄄33.
(LEIXiaohui,TIANYu,BAIWei,etal.
TheimprovingandapplicationofwatershedsubdivisionmethodbasedonDEM[J].
YellowRiver,2011,33(2):32鄄33.
(inChinese))[16]张峰,廖卫红,雷晓辉,等.
分布式水文模型子流域划分方法[J].
南水北调与水利科技,2011,9(3):101鄄105.
(ZHANGFeng,LIAOWeihong,LEIXiaohui,etal.
Areviewonsub鄄basindelineationmethodsfordistributedhydrologicalmodels[J].
South鄄to鄄NorthWaterDiversionandWaterScience&Technology,2011,9(3):101鄄105.
(inChinese))[17]王皓,李铁键,高洁,等.
大尺度流域河网二叉树编码方法[J].
河海大学学报:自然科学版,2009,37(5):499鄄504.
(WANGHao,LITiejian,GAOJie,etal.
Binary鄄treecodingfordrainagenetworkoflarge鄄scalebasins[J].
JournalofHehaiUniversity:NaturalSciences,2009,37(5):499鄄504.
(inChinese蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚蕚))·简讯·东亚环境社会学国际研讨会将在河海大学召开东亚环境社会学国际研讨会拟定于2013年11月2—4日在河海大学召开.
本次会议由河海大学公共管理学院、中国人民大学社会学理论与方法研究中心、中央民族大学社会学系、中国社会学会环境社会学专业委员会主办,河海大学社会学系、环境与社会研究中心承办.
会议以"多样性:环境与社会冶为主旨,希望发掘更多的地方经验,建构有效的行动策略,探寻人类共同的出路.
东亚地区是社会文化多样性最典型的地区之一.
面对日益严峻的环境问题,不同地区正在探寻各自的应对策略,也正在积累地方经验.
如何加强沟通,凝聚共识,应对共同的环境挑战,是摆在人们面前的重要议题.
会议研讨专题主要包括:(a)环境社会学理论;(b)水生态·水社会·水文化;(c)后福岛时代的能源政策;(d)生态问题与人口迁移;(e)环境与健康;(f)地方知识与地域经验;(g)环境意识与环境教育;(h)NGO与环境运动;(i)自然资源管理与环境治理;(j)气候变化与社区发展;(k)环境社会学的学科发展.
会议的相关信息请浏览网站:http://www.
hhu.
edu.
cn/s/1/t/7/67/0a/info26378.
htm(本刊编辑部供稿)392