测绘学报

• 学术论文 •    

基于等高线Delaunay三角网的等高线树生成方法

张尧1,樊红2,黄旺2   

  1. 1. 四川省基础地理信息中心
    2. 武汉大学
  • 收稿日期:2011-05-16 修回日期:2012-01-17 出版日期:2012-06-25 发布日期:2012-06-25
  • 通讯作者: 张尧

The Method of Generating Contour Tree Based on Contour Delaunay Triangulation

  • Received:2011-05-16 Revised:2012-01-17 Online:2012-06-25 Published:2012-06-25

摘要: 等高线树是表达等高线空间关系的有效手段,能明确地表现等高线的邻接和包含关系,为等高线的其它处理提供便利。本文研究如何利用Delaunay三角网构建等高线树,提出了一种新的等高线树生成方法。该方法充分利用Delaunay三角网在领域分析中的优势,通过两次利用Delaunay三角网来判明等高线的空间关系进而达到统一被图廓截断的等高线以生成等高线树的目的。本文将等高线作为约束边构建约束型Delaunay三角网,利用Delaunay三角网查找具有邻接关系的等高线,在此基础上结合邻近等高线的高程关系判明、识别,最终统一被截断的等高线;然后对统一后的等高线再次利用Delaunay三角网查找具有邻接关系的等高线对,利用等高线对的高程关系判断出其为父子关系或兄弟关系,据此将等高线插入到相应的位置,逐步生长成等高线树。本文同时给出了基于Delaunay三角网的等高线树生成方法的算法设计及实验结果。

Abstract: Contour tree is an effective method to express the spatial relations of contour lines. The adjacent relationship and inclusion relationship of contour lines can be expressed clearly by contour tree. Contour tree facilitates the processing of contour lines. This work studies how to construct contour tree by using of Delaunay triangulation, proposes a new method of generating contour tree. It fully uses the advantages of Delaunay triangulation in Domain Analysis, determines the spatial relationship of contour lines by using Delaunay triangulation twice, then unifies these contour lines which are truncated by figure profile to achieve the purpose of generating contour tree. In this work contour lines are used as a constraint edge to build a constrained Delaunay triangulation. Contour lines with neighboring relations are found by using of Delaunay triangulation. On this basis, the truncated contour lines are ascertained, identified and unified ultimately through combining the elevation of their neighboring contour lines. Then the two contour lines with neighboring relations are found again after the contour lines reunification by using of Delaunay triangulation. By using the elevation of the two contour lines to judge whether they are brothers or father-son relationship. The contour lines are inserted into the appropriate position in tree according to the relationship. And the contour tree grows gradually. This paper also gives algorithm design of the method of generating contour tree based on Delaunay Triangulation and experimental results.