基于区间树索引的等高线提取算法

《基于区间树索引的等高线提取算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2007年2月GeomaticsandInformalionScienceofWuhanUniversityFeb.2007文献标志码：A文章编号:1671-8860(2007)02-0131-04基于区间树索引的等咼线提取算法王涛】毋河海2刘纪平1（1中国测绘科学研究院，北京市北太平路16号,100039）（2武汉大学资源与环境科学学院•武汉市珞喻路129号,430079）摘要：重新设计了从高程格网中提取等高线过程中的遍历策略，以保证提取结果具有统一的方向；针对日益增长的高程格网数据量，提出了基于区间树索引来查找等高线起点的算法。关键词：等高线；

2、高程格网；提取算法；区间树中图法分类号:P283.7；P231.5收稿日期：2006-10-25.项目來源：地理空间信息工程国家测绘局复点实验室开放研究基金资助项目（132526,2534）；辽宁工程技术大学地理空间信息技术力•为'徽嚴验室幵放研究基金资助项目（2006003）。格网DEM和等高线作为地形表达的两种重要方式，各有独特的优势，二者之间的相互转换是计算机制图和地理信息系统的基本功能之一。从格网DEM中内插提取等高线的算法较多但随着各种地形数据获取手段的改进，传统的从地形等高线内插生成格网DEM的状况发生了极大的改变，直接秋取的格网DEM

3、数据在数量和质量上都得到了极大的提高，从格网DEM中提取等高线将会成为算法的常用功能，因此迫切需要高效率的等高线提取算法。1格网DEM中的等高线提取1.1算法的基本过程首先，在格网中确定待内插等高线的起点；然后，从起点出发确定下一个等高点并连接成等高线，直至边界或者回到出发点。1.2顾及方向的策略在数字环境下，等高线的方向是表达地形的基本耍素之一，各种基于等高线的数字地形分析算法要求等高线在全区域内具有固定一致的方向（左高右低或者左低右高），如地性线的自动提取⑷。以往等高线提取算法没有顾及这个问题,必须经过后续处理才能使得等高线具有统一的方向闪O为

4、了使提取的等高线自动具有一致化的方向，需要对现有算法中起点确定和遍历方向进行修正。假设高程网格左上角为原点，向右、向下分别为工轴」轴正向，在网格的-T轴方向上寻找闭合曲线起始单元边时，简化判断条件，将原始条件的（Z—乙）X（Z—乙）＜0修改为Z〉乙且z＜乙（乙在乙左侧），在确定下一点时只考虑.y轴正方向（向下）。如图1中，当提取高程为8的闭曲线时，只考虑7-10和6-11两条边，若选前者作为起点，其后续点将考虑6-11,而不是垂直边7-9。分析高程格网屮等高线的特点可知，闭曲线至少经过一条左高右低的网格边，因此，这一简单的修改不但不会影响最终结果，

5、而且保证了等高线在任意正负地貌表达上的左高右低。基于同样的原则，在边界上提取开曲线时可以作类似的修改以得到方向一致的结果⑹。该策略在简化判断条件、提高效率的同时，还为进一步引入索引结构<~<—49910图1有向等鬲线的提取Fig.1ExtractionofDirectedContour提供了可能。2基于区间树索引的算法使用§1的简化条件确定起始点來提取某一特定高程等高线时，可能的起始网格边比以往算法可以降低一半左右，不过这种方法的平均运行效率仍旧足0（"）,当等高线所经过的格网单元数相对很少或者分布零散时，效率还不高。在髙程维上，新的起始网格边是一

6、个由左到右的增序区间。确定等高线起点的操作相当于在该起始边集合中找到一个合适的区间元素，这样就可以引入区间树索引来提高该步骤的效率［⑷。作为一维空间上的索引，区间树是一种有序二叉树，它可以提高二维平面上矩形相交探测的效率⑶，每个节点上记录多个区间元索，其上的每个区间左右端点值分处该节点关键值左右，而英左子树上节点所含区间元素的左右端点值都小于父节点关键值，右子树上节点所含区间元索相反。区间树索引的对象也即节点元素是数值区间，因此在构建和查询等操作上与普通的二叉树有较大的差异。区间树的构建和查询效率强烈依赖于各级节点的关键字（分割值）的设定，即便是相

7、同的关键字，如果给定的顺序不同，对树结构也有较大影响，因此在构建区间树的预处理过程屮，应当选择合适关键字，以充分顾及树的平衡程度、深度和各节点中元素个数等三方面因素的均衡。2.1区间树索引的构建最简单而快速的构建区间树索引方法是按照高程范围逐级取平均值作为关键字，但是这种方法显然不可能使得上述3个因素在树结构中得到均衡。最好的方法是在构建树之前对所有的可能起始单元边按照左端点（或者右端点）高程进行排序，然后逐层确定单元边数目的中位数，将该位置的高程作为各级节点的关键字，但是对于大数据量的高程格网而言，精确的排序过程将会使得构建过程显得效率低下。本文

8、采用了直方图累积值的分段来逼近这一结果，并据此得到一系列关键字，然后构建一棵空树，最后将可能的起始单元边填充进去。具体的构