《基于相邻关系的等高线树建立算法研究.doc》由会员分享，可在线阅读，更多相关《基于相邻关系的等高线树建立算法研究.doc（6页珍藏版）》请在金锄头文库上搜索。
1、基于相邻关系的等高线树建立算法研究郭沛沛 李成名 殷 勇 丁圣陶（中国测绘科学研究院地图制图学与地理信息系统研究所，北京 海淀区 100830，）摘 要 等高线树在提取地形线、地貌综合等方面具有重要的应用意义。常用的等高线树表达的是等高线的层次关系，直接表达等高线的包含和邻接关系，建树过程复杂，对数据要求较高，需要对数据进行预处理。本文对图幅内等高线按照是否闭合分为两类，分别对两类等高线群进行建树，最后将两个独立的等高线树合并，形成完整的等高线树。最后生成的等高线树表示了等高线之间的相邻关系，再借助其高程值就可以判断出等高线之间的包含邻接关系，算法容易理解，程序实现简单。关键词 等高线树；相邻
2、关系；高程值；闭合等高线；不闭合等高线An Algorithm Of Neighbor Relationship Oriented Contour Tree BuildingGuo Peipei, Li Chengming, Yin Yong, Ding Shengtao（the Institute of Cartography and Geographic Information System of Chinese Academy of Surveying and Mapping 100830）Abstract: A contour tree has found many important
3、 applications in extraction of terrain structure lines, terrain analysis etc. A regular contour tree expressing the spatial relationship of contours is difficult to build,even with data of high quality.A new method is proposed in this paper:classify contours into close group and open group; build co
4、ntour tree for each group respectively;finally amalgamate these two contour trees into one.With the elevation values, spatial relationship of contours is of easy accessibility. The result shows that the above mentioned method is correct and effective.Key Words:contour tree; neighbor relationship; el
5、evation value; close contour; unclosed contour;1 引言等高线之间的空间关系通常采用等高线树来表达。等高线树表达的是等高线之间的层次关系，表现为等高线之间隶属/包含的父子关系，邻接/并列的兄弟关系等。等高线树在地表形态组成分析、地貌综合等等中应用很广泛1。现有的等高线树，父子节点直接表示等高线之间的包含关系，兄弟节点之间表示邻接关系。在建立过程中，最重要的一步是进行等高线闭合方向的正确判断。但是现有判断方法得到的结果往往存在二义性，有时得到的结果和实际情况会有差异。2 算法概述首先对图幅内所有等高线进行识别，分为闭合和不闭合等高线两类。对于闭合等高
6、线，直接使用现有方法建立闭合等高线树CloseTree；对于每一条不闭合等高线，它必定和图幅边有两个交点。求出所有交点，按照沿图幅边逆时针方向排序，记录它们的序号。假设存在两条等高线L1、L2，它们的起点序号分别为S1、S2，终点分别为E1、E2。如果S1 = S21并且E1= E2 + 1，则L1和L2相邻，且在L2一侧只和L2相邻；如果S1 = S21或者E1= E2 + 1，则L1和L2相邻，但不唯一和L2相邻。依此建立不闭合等高线树结构OpenTree。最后将两个树进行合并，得到整个等高线图幅的关系。如果不同高程的两条相邻等高线具有包含关系，相同高程的两条相邻等高线并列/邻接关系。3
7、算法具体步骤3.1 等高线识别分类读取图幅内所有等高线，判断等高线是否闭合。如果闭合，将其ID放入数组closeIDs中；如果不闭合，计算它和图幅边的交点，放入到数组intersectNodes中。对intersectNodes中的交点，按照交点沿着图幅边到图幅左下角点的距离升序排列。3.2 闭合等高线建树取closeIDs中存储的所有闭合等高线，按照等高线形成的闭合面的面积由小到大排序。取面积最小且没有处理过的等高线Li，判断其余闭合面面积较大的等高线Lj和它的包含关系：可以首先取Li上任一点Pi，判断其余等高线Lj是否包含Pi。如果Lj不包含Pi， 则Lj肯定不包含Li；如果Lj包含Pi，
8、则需要进一步判断Lj是否包含Li上全部点。确定等高线之间的包含关系后按照下面方法，建立树结构。3.2.1 按面积排序：按照等高线形成的闭合面的面积升序排列，得到等高线序列。3.2.2 按包含关系分组：取闭合面积最小等高线上任一点，判断其余等高线对它的包含关系，得到一组等高线，并且标记这组等高线，它们不再作为面积最小等高线进行判断。再取面积最小且没有标记的等高线，同样方法得到一组等高线最后得到若干组包含关系的等高线群ContainContourGroups,。 3.2.3 建立子树：对ContainContourGroups中的每一组进行分类，最后一个等高线相同的组划分为一类。对每一类包含关系等
9、高线群处理。对于每一类，把这类中每一组的序号颠倒过来。建立一个子树，它的根节点包含的数据为各组的第一个等高线，取各组等高线群的第二个等高线，建立子节点，把第一个等高线节点作为父节点。如果各组等高线群的第二个等高线有重复的，只建立一个子节点。依次取各组等高线群的第二个、第三个.等高线进行前述操作，直到所有组的等高线都搜索结束，同样方法建立下一类对应的子树。3.2.4 建立闭合等高线树：把每个子树的根节点作为子节点，加入到总的闭合等高线树中。最后建立的闭合等高线树CloseTree。如图1中所示：按照等高线形成的闭合面的面积升序排列，得到序列9，5，8，6，7，0，4，3，10，2，1；按照包含关
10、系分组得到等高线群ContainContourGroups： L9，L10， L5，L4，L3，L2，L1，L7，L10，L8，L10，L6，L2，L1，L0 ; 将其划分为3类，分别建立子树。最后建立的闭合等高线树CloseTree如图1下所示：图1 闭合等高线及其对应的等高线树结构CloseTree.3.3 不闭合等高线建树3.3.1 确定起始等高线：对IntersectNodes中所有点Ni（i是交点的序号，如果Ni为最后一个交点，则Ni+1是第一个交点）进行判断，如果满足Ni和Ni+1在同一条等高线Lk上，则把Lk添加到起始等高线组StartContours中，并且对Ni和Ni+1进行
11、标记。对起始等高线组中的每一个等高线创建一个独立节点，进入3.3.2。如图2所示，起始等高线为L13、L15、L19、L17、L7、L9、L1。3.3.2 搜索结束的条件：对起始等高线组中的等高线按照起点序号的大小排序，然后判断前一条等高线的终点是否直接和后一条等高线的起点相邻（即中间不相隔其他的交点）。最后一条等高线的终点和第一条等高线的起点相比。如果有一个不满足的情况，则表示搜索没有结束。如果满足要求，则把起始等高线对应的节点作为子节点，添加到以整个图幅作为根节点的树结构中。对3.3.1中的结果判断是否结束，如果没有结束则进入3.3.3。图2中，由于L13终点的后一个交点明显和L15的起点
12、不相邻，搜索未结束。3.3.3 寻找唯一相邻等高线：对起始等高线中的等高线Ci，它的起点和终点分别为：Ns，Ne（s和e表示交点的序号，第一个交点的前一个交点是最后一个交点，最后一个交点的下一个交点是第一个交点）。判断Ns的前一个交点Ns-1和Ne的后一个交点Ne+1是否在同一个等高线上。如果位于同一个等高线Cj上，则Cj和Ci相邻，并对等高线Cj创建节点，作为Ci节点的父节点，并用Cj代替Ci存放到起始等高线组StartContours中，对Cj的起点和终点Ns-1、Ne+1进行标记，再对Cj进行Ci一样的操作；如果不位于同一个等高线上，则不进行其他操作。对起始等高线中的每一个等高线进行同样
13、的操作。图2中L13搜索得到的等高线为L12、L15的搜索得到的等高线为L14、L19的搜索得到的等高线为L18、L17没有搜索到唯一相邻等高线、L7的搜索得到的等高线为L6、L9的搜索得到的等高线为L8、L1的搜索得到的等高线为L2、L3。此时起始等高线组中的等高线为L12、L14、L18、L17、L6、L8、L3。所有的起始等高线处理结束后，判断搜索是否结束，不结束则进入3.3.4。图中L12的终点和L14的起点不相邻，故搜索未结束。3.3.4 合并起始等高线组：对于起始等高线组中的等高线，按照起点的位置升序排序。找出其中连续相邻的起始等高线Ci，Cj.Ck，这里的连续相邻是指前一个等高线
14、的终点与后一个等高线的起点相邻。判断它们中第一个等高线Ci起点的前一个节点和它们中最后一个等高线Ck终点的后一个节点是否未标记且在同一个等高线上。若是，且他们在同一个等高线Ci上，则对Ci建立节点，把这些起始等高线对应的节点作为Ci对应节点的子节点，并从起始等高线组中删除这些起始等高线。对Ci的起点和终点进行标记。图2中L16代替L17、L18，L5代替L6、L8，此时起始等高线变为L12、L14、L16、L5、L3。判断搜索是否结束，不结束则进入3.3.3。图中L12的终点和L14的起点不相邻，故搜索未结束，进入3.3.3继续搜索。整个建树的过程和结果不闭合等高线树OpenTree如图所示。
15、图2 不闭合等高线及其对应的等高线树结构OpenTree3.4 建立整个等高线树前面两步建立的等高线树是相互独立的，这一步就是要把闭合和不闭合等高线树结合起来，表示出图幅内所有等高线的空间关系。具体步骤如下：3.4.1 对CloseTree根节点的所有子节点cNODEi，取它们代表的闭合等高线Ci。同时，对OpenTree根节点的所有子节点oNODEj，取它们代表的不闭合等高线Cj。如图3，下侧左边的树为CloseTree，其根节点的子节点代表的等高线为L14，L15，L16，L17，下侧右边的树为OpenTree，其根节点的子节点代表的等高线为L10，L11，L12。3.4.2 对于Cj，按
16、照等高线起点到终点的方向，沿着图幅边进行闭合，形成闭合等高线Cj。判断Cj是否包含Ci。如果不包含，取OpenTree根节点的下一个子节点进行同样的判断；如果包含，将此oNODEj当做根节点重复3.4.2。如果OpenTree根节点的所有子节点都不包含Ci，则把Ci添加到OpenTree中，图幅根节点作为cNODEi的父节点。3.4.3 直到遇到父节点包含Ci，但所有子节点都不包含Ci的情况，把此父节点作为cNODEi的父节点。取闭合等高线树根节点的下一个子节点，进入3.4.2。如图3所示，对于等高线L14，它被等高线L10和图幅左上角点形成的闭合环包含，但是不被等高线L13与图幅左上角点形成的闭合环包含，因此把L14对应的节点作为L10对应节点的子
