一种剖分平面多边形的通用算法描述  

Description of a New Trapezoidation Algorithm for Planar Polygons

作　　者：叶琳[1] 邱龙辉[1] 

机构地区：[1]青岛化工学院机械工程系,山东青岛266042

出　　处：《计算机与现代化》2002年第7期4-6,11,共4页Computer and Modernization

摘　　要：提出了一种用梯形来剖分非单调平面多边形的通用算法 ,算法包括三部分 :初始化、梯形化和优化 (后处理 ) ,所处理的多边形可以包含孔 ,孔可以嵌套。本算法的时间复杂度是O(n2 log2 n)。Describes a new algorithm for decomposing non monotone planar polygons to trapezoids. The algorithm consists of three parts: initialization, trapezoidation and post processing. The polygons may contain holes, and the holes may be nested and have common edges.

关 键 词：平面多边形 通用算法 梯形化 计算机图形学 几何图形 多边形剖分 

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