加权扫描三角剖分简单多边形

• 作 者: 肖忠晖 卢振荣
• 机 构: 交通大学机械工程学院
• 出 处: 首届中国计算机图形学学术会议
• 发表日期: 1996年期
• 关键词: 加权 扫描 三角剖分 剖分算法 三角形 多边形 权值函数 复杂度 顶点数 质量 形态 理论 基础 概念 方法

在多边形的三角剖分算法中，从概念的角度看，切耳算法是最简单的；而从理论的角度看，Ｄｅｌａｕｎａｙ三角剖分算法是最优的。该文通过建立三角形的权值函数，以切耳算法为基础，提出用加权扫描的方法来实现简单多边形Ｐ的三角剖分。该文确立的算法的时间复杂度为Ｏ（ｎ〈’２〉），其中ｎ为Ｐ的顶点数，剖分获得的三角形的形态质量非常好。