轮廓线位置关系判定的改进算法.docVIP

轮廓线位置关系判定的改进算法 贺怀清，杨 鹏 ( 中国民航大学 计算机科学与技术学院，天津 300300) ( huaiqinghe@ yahoo． com． cn; yangpeng686@ 163． com) 摘 要: 通过对射线法和坐标极值法的原理和存在的问题进行分析，对已有的轮廓线走向判定算法进行简化，结 合射线法和坐标极值法的优点，提出一种改进的轮廓线位置关系判定算法。该算法主要包括 4 个部分: 内外轮廓线的 区分、调整轮廓线的走向、轮廓线的包容识别和轮廓树的构建。通过实验验证，改进的算法能够更正已有算法中存在 的问题，同时能够获得较好的运行效率。 关键词: 轮廓线; 射线法; 坐标极值法; 位置关系; 轮廓树 中图分类号: TP751． 1; TP391． 72 文献标志码: A Improved algorithm on contour line position relation HE Huai-qing， YANG Peng ( College of Computer Science and Technology， Civil Aviation University of China， Tianjin 300300， China) 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 高了运算速度。但是这个算法在面对凹多边形时会得到错误 的结果。如图 1 中，轮廓线之间的位置关系较复杂，虚线表示 坐标极值围成的区域，当采用坐标极值判别法时，g 的包容轮 廓线就是 c 而不是 a，因而不能得到正确的相邻轮廓线的包容 关系。 0 引言 快速成型( Rapid Prototyping，RP) 技术采用了离散 / 堆积 成形的概念［1］。在离散堆积过程中，当 模 型 切 片 后，同 一 截 面上可能同时包含多条轮廓线，这些轮廓线之间存在不同的 位置关系。轮廓线的位置关系界定了实体填充的区域，因 而 它是快速成型系统中填充算法的基础。 目前相对成熟的算法 主 要 包 括: 射 线 法［2 － 3］ 和 坐 标 极 值 法［4 － 5］。文献［2］通过找到轮廓线的特征点，根 据 从 特 征 点 引出的射线同其他轮廓线的交点情况来判断轮廓线之间的位 置关系; 文献［3］从轮廓线上任取一点向左或向右 引 水 平 射 线，根据射线同其他轮廓线的交点个数来判断位置关系，这种 算法由于要对多边形求交，在多边形边数较多时，效率 较 低， 同时在内轮廓线的最邻近包容轮廓线识别算法上有一定的缺 陷; 文献［4］对坐标极值判别法进行了详细的描述，首先求出 各轮廓线的坐标极值点，通过比较各轮廓线间坐标极值点的 关系来判定位置 关 系; 文 献［5］提出利用最小矩形 面 积 来 确 定轮廓线间的位置关系，最小矩形即为轮廓线的坐标极值点 构成