论文部分内容阅读
简单多边形的三角形化不但在图形显示及数值分析计算的表面插值等实际应用方面有重要作用，而且在解决计算几何本身的一些问题中也是一个强有力的工具。Ｇｒａｈａｍ扫描在计算几何中是一种基本的后追综技术。Ｇｒａｈａｍ扫描与切耳朵算法结合可获得一个三角形化简单多边形的Ｏ（ｋｎ）时间算法，其中Ｋ－１是凹顶点的个数，算法在最坏情况为Ｏ（ｎ＜’２＞）。算法表达多边形的数据结构为双向循环链表。算法描述准确、简炼，运行快速，易于应用。