一种凹角消去的多边形三角化方法  

A Concave-Angle-Removing Polygon Triangulation

作　　者：任婉[1] 刘基伟[1] 

机构地区：[1]新乡医学院,河南新乡453003

出　　处：《河南科技学院学报》2008年第3期136-138,共3页Journal of Henan Institute of Science and Technology(Natural Science Edition)

摘　　要：多边形三角化问题是计算几何中的一个经典问题,并在图形学中广泛应用。本文首先分析了凹角对于多边形形状(凹或凸)的重要作用;然后提出迭代的凹角消去的三角化算法。从凹角发出的射线把多边形分块使之转化为多个凸多边形,最后三角化凸多边形。本方法算法实现简易,易于理解,经过试验,取得了预期的效果。Polygon triangulation problem is among the most classic problem in computational geometry, and gets great concern in computer graphics. In this paper we discuss the importance of concave angle in polygons, and then present a concave - angle - removing polygon triangulation method. Lines emitting from concave vertices break polygon into sub - polygons and break concave angle into two convex angles. While all sub - polygons become convex, a triangulation of convex polygon is followed. This method is easy to understand and after the implementation, we show the validitv of our method

关 键 词：多边形三角化 y轴水平线算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]