Abstract: By analyzing the principle and the existing problems in the ray method and the extreme coordinate value method, the existing algorithms which determined contour direction were simplified. Then an improved algorithm on the contour line position relation was proposed combining the advantages of the ray method and the extreme coordinate method. The algorithm mainly included four parts: distinction among the internal and external contours, adjustment of the profile direction, inclusive identification of contours and the construction of a contour tree. The experimental results show that the improved algorithm can correct the problems in the existing algorithms and achieve good efficiency.

Key words: contour line, ray method, extreme coordinate value method, position relation, contour tree

摘要： 通过对射线法和坐标极值法的原理和存在的问题进行分析,对已有的轮廓线走向判定算法进行简化,结合射线法和坐标极值法的优点,提出一种改进的轮廓线位置关系判定算法。该算法主要包括4个部分:内外轮廓线的区分、调整轮廓线的走向、轮廓线的包容识别和轮廓树的构建。通过实验验证,改进的算法能够更正已有算法中存在的问题,同时能够获得较好的运行效率。

关键词: 轮廓线, 射线法, 坐标极值法, 位置关系, 轮廓树