《1 前言》

1 前言

等高线之间的空间关系通常采用等高线树来表示。等高线树表达的是等高线之间的层次关系，表现为等高线之间隶属/包含的父子关系和邻接/并列的兄弟关系等。等高线树在地表形态组成分析和地貌综合等方面应用很广泛[1] 。现有的等高线树中父子节点直接表示等高线之间的包含关系，兄弟节点直接表示邻接关系。在建立过程中，最重要的一步是进行等高线闭合方向的正确判断。但是现有判断方法得到的结果往往存在二义性，有时得到的结果和实际情况会有差异。

基于相邻关系的等高线树中当前节点和它的子节点、父节点之间具有邻接关系。借助等高线的高程信息就能判断出相邻等高线之间的包含关系。等高线树的生成确立了等高线空间关系，为提取地性结构线提供了便利的条件和基础。以提取谷底线为例，从最高高程开始，向下寻找谷底点时的搜索范围因为有了等高线树才大大缩小，只需在与当前等高线相邻的低高程等高线上寻找。如果仅靠距离限制，那么有可能追踪到邻近山头所涉及的等高线上。使用等高线树可使搜索的正确性及速度大大提高[2] 。

《2 算法概述》

2 算法概述

首先对图幅内所有等高线进行识别，分为闭合等高线和不闭合等高线两类。对于闭合等高线，直接使用现有方法建立闭合等高线树 Close Tree；对于每一条不闭合等高线，它必定和图幅边有两个交点。求出所有交点，按照沿图幅边逆时针方向排序，记录它们的序号。假设存在两条等高线L1、L2，它们的起点序号分别为 S1、S2，终点分别为 E1、E2。如果S1 = S2–1并且 E1= E2 + 1，则L1和L2相邻，且在 L2一侧只和L2相邻；如果S1 = S2–1或者E1= E2 + 1，则L1和L2相邻，但不唯一和L2相邻。依此建立不闭合等高线树结构Open Tree。最后将两个树进行合并，得到整个等高线图幅的关系（见图1）。如果不同高程的两条相邻等高线具有包含关系，则相同高程的两条相邻等高线具有并列/邻接关系。

《图1》

图1 相邻关系等高线树的建立流程

Fig.1 Process of building the contour neighbor Tree

《3 算法具体步骤》

3 算法具体步骤

《3.1 等高线识别分类》

3.1 等高线识别分类

读取图幅内所有等高线，判断等高线是否闭合。如果闭合，将其 ID 放入数组 closeIDs[]中；如果不闭合，计算它和图幅边的交点，放入到数组 intersectNodes[]中。对 intersectNodes[]中的交点，按照交点沿着图幅边到图幅左下角点的距离升序排列。

《3.2 闭合等高线建树》

3.2 闭合等高线建树

取closeIDs[]中存储的所有闭合等高线，按照等高线形成的闭合面的面积由小到大排序。取面积最小且没有处理过的等高线Li，判断其余闭合面面积较大的等高线Lj 和它的包含关系：可以首先取Li上任一点Pi，判断其余等高线Lj 是否包含Pi 。如果Lj 不包含Pi，则Lj 肯定不包含Li；如果Lj 包含Pi，则需要进一步判断Lj 是否包含Li 上全部点。确定等高线之间的包含关系后按照下面方法，建立树结构（见图2）。

《图2》

图2 闭合等高线树建立过程

Fig.2 Process of building the Close Tree

1）按面积排序。按照等高线形成的闭合面的面积升序排列，得到等高线序列。

2）按包含关系分组。取闭合面积最小的等高线上任一点，判断其余等高线对它的包含关系，得到一组等高线，并且标记这组等高线，它们不再作为面积最小等高线进行判断。再取面积最小且没有标记的等高线，同样方法得到一组等高线……最后得到若干组包含关系的等高线群ContainContourGroups[[]，[]，[]…]。

3）建立子树。对ContainContourGroups中的每一组进行分类，最后一个等高线相同的组划分为一类。对每一类包含关系等高线群进行处理。对于每一类，把这类中每一组的序号颠倒过来，建立一个子树，它的根节点包含的数据为各组的第一条等高线，取各组等高线群的第二条等高线，建立子节点，把第一个等高线节点作为父节点。如果各组等高线群的第二条等高线有重复的，只建立一个子节点。依次取各组等高线群的第二条、第三条……等高线进行前述操作，直到所有组的等高线都搜索结束，同样方法建立下一类对应的子树。

4）建立闭合等高线树。把每个子树的根节点作为子节点，加入到总的闭合等高线树中。最后建立的闭合等高线树Close Tree。

如图3所示，按照等高线形成的闭合面的面积升序排列，得到序列[9，5，8，6，7，0，4，3，10，2，1]；按照包含关系分组得到等高线群 ContainContourGroups[]：[ [L9，L10]，[ L5，L4，L3，L2，L1]，[L7，L10]，[L8， L10]，[L6，L2，L1]，[L0] ]；将其划分为 3 类，分别建立子树；最后建立了闭合等高线树Close Tree。

《图3》

图3 闭合等高线及其对应的等高线树结构Close Tree

Fig.3 Close contours and the corresponding Close Tree

《3.3 不闭合等高线建树》

3.3 不闭合等高线建树

不闭合等高线的建树过程如图4所示。

《图4》

图4 不闭合等高线的建立过程

Fig.4 Process of building the Open Tree

1）确定起始等高线。对intersectNodes[]中所有点 Ni （i 是交点的序号，如果Ni为最后一个交点，则 Ni +1是第一个交点）进行判断，如果满足Ni 和Ni +1在同一条等高线 Lk上，则把 Lk 添加到起始等高线组 StartContours[]中，并且对Ni 和Ni +1进行标记。对起始等高线组中的每一条等高线创建一个独立节点，进入2）。

如图5所示，起始等高线为L13、L15、L19、L17、L7、L9 和L1。

《图5》

图5 不闭合等高线及其对应的等高线树结构Open Tree

Fig.5 Open contours and the corresponding Open Tree

2）搜索结束的条件。判断是否所有的节点都被搜索过了，如果不是则表示没有结束，继续下一步；如果是，则把起始等高线对应的节点作为子节点，添加到以整个图幅作为根节点的树结构中。

对1）中的结果判断是否结束，如果没有结束则进入3）。

3）寻找唯一相邻等高线。对于起始等高线中的等高线 Ci，它的起点和终点分别为 Ns 和 Ne（s 和 e 表示交点的序号，交点N0的前一个交点是N2n，交点 N2n的下一个交点是 N0，共有 n 条等高线）。判断 Ns 的前一个交点Ns-1和Ne 的后一个交点Ne+1是否在同一条等高线上。如果不位于同一条等高线上，则不进行其他操作；如果位于同一条等高线 Cj 上，则Cj 和 Ci 相邻，并对等高线 Cj 创建节点，作为Ci 节点的父节点，并用 Cj 代替Ci 存放到起始等高线组 StartContours[]中，对 Cj 的起点和终点Ns-1、Ne+1进行标记，再对 Cj  进行与 Ci 一样的操作。对起始等高线中的每一条等高线进行同样的操作。

所有的起始等高线处理结束后，判断搜索是否结束，不结束则进入4）。

4）合并起始等高线组。对于起始等高线组中的等高线，按照起点的位置升序排序。找出其中连续相邻的起始等高线[Ci ， Cj ，…，Ck ]，这里的连续相邻是指前一个等高线的终点与后一个等高线的起点相邻。判断它们中第一条等高线 Ci 起点的前一个节点和它们中最后一条等高线 Ck 终点的后一个节点是否未标记且在同一条等高线上。若是，且它们在同一条等高线 Ci 上，则对Ci 建立节点，把这些起始等高线对应的节点作为 Ci 对应节点的子节点，并从起始等高线组中删除这些起始等高线。对 Ci  的起点和终点进行标记。

判断搜索是否结束，不结束则进入3）。

整个建树的过程和结果及不闭合等高线树 Open Tree如图5所示。

《3.4 建立整个等高线树》

3.4 建立整个等高线树

前面两步建立的等高线树是相互独立的，这一步就是要把闭合和不闭合等高线树结合起来，表示出图幅内所有等高线的空间关系，具体步骤如下。

1）对Close Tree根节点的所有子节点cNODEi，取它们代表的闭合等高线 Ci 。同时，对Open Tree根节点的所有子节点 oNODEj，取它们代表的不闭合等高线 Cj 。

如图 6 所示，下侧左边的树为 Close Tree，其根节点的子节点代表的等高线为 L14、L15、L16和 L17，下侧右边的树为Open Tree，其根节点的子节点代表的等高线为L10、L11和L12。

《图6》

图6 闭合等高线树、不闭合等高线树及完整等高线树的建立

Fig.6 Close Tree，Open Tree and process of building the contour neighbor Tree

2）对于Cj ，按照等高线起点到终点的方向，沿着图幅边进行闭合，形成闭合等高线Cj′ 。判断Cj′ 是否包含Ci 。如果不包含，取Open Tree根节点的下一个子节点进行同样的判断；如果包含，将此oNODEj当作根节点重复2）。如果Open Tree根节点的所有子节点都不包含Ci ，则把Ci 添加到Open Tree中，图幅根节点作为cNODEi 的父节点。

3）直到遇到父节点包含Ci，但所有子节点都不包含Ci 的情况，把此父节点作为 cNODEi 的父节点。取闭合等高线树根节点的下一个子节点，进入2）。

如图 6 所示，对于等高线 L14，它被等高线 L10和图幅左上角点形成的闭合环包含，但是不被等高线 L13与图幅左上角点形成的闭合环包含，因此把节点 L14作为节点 L10的子节点。对于等高线 L17，判断出 L11与图幅边角点形成的闭合环没有包含关系；但判断出和下一个子节点 L12有包含关系；和 L12的子节点 L7也有包含关系；但和 L7的子节点 L5和 L4都没有包含关系，因此把 L17作为 L7的子节点。

4）当Close Tree根节点所有的子节点都找到父节点，等高线树建立完毕。

《4 结语》

4 结语

树结构是表达等高线空间关系的一种良好工具，如何正确快速地对大数据量的等高线数据建立树结构对于提取地形线和地貌综合等工作具有重要意义[3，4] 。本文提出一种基于等高线相邻关系生成等高线树的新方法，此方法简单易懂，不需要预处理，便于使用计算机程序实现。经过实际程序验证，其对闭合不闭合等高线均能处理。