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

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

The Method of Generating Contour Tree Based on Contour Delaunay Triangulation

The Delaunay triangulation is employed to construct the contour tree and a new method of generating contour tree is proposed.By making full use of its advantages in domain analysis,the Delaunay triangulation is used twice to determine the spatial relationship between contour lines,thus contour lines that are truncated by map margin can be integrated to generate the contour tree.First of all,contour lines are used as constraint edges to build a constrained Delaunay triangulation,which is in turn used to find neighboring contour lines,thus the truncated contour lines can be ascertained,identified and integrated ultimately by combining elevations of the contour lines around.And then the Delaunay triangulation is employed again to find the contour line pairs with adjacency relation.The relationship between a line pair,either brotherhood or parent-child relation,depends on their elevations,and the contour lines are inserted into the appropriate position in tree according to the relationships.At last the contour tree grows gradually.The implementation of algorithm to generate the contour tree based on Delaunay triangulation and experimental results are provided.