一个通用的快速三角化算法  

A General and Fast Triangulation Algorithm

作　　者：李伟青[1] 彭群生[1] 

机构地区：[1]浙江大学CAD&CG国家重点实验室,杭州310027

出　　处：《计算机辅助设计与图形学学报》2001年第9期769-773,共5页Journal of Computer-Aided Design & Computer Graphics

基　　金："创新研究群体科学基金"(60 0 2 12 0 1)资助

摘　　要：提出了一个适用于任意平面多边形区域及散乱点集的通用三角化算法 .当算法应用于多边形区域时 ,首先对各个顶点和区域内部的散乱点按扫描方式排序 ,然后依次扫描各点 ,扩展生成新的三角形 ,从而获得局部已剖分区域 ,并最终完成整个区域的三角化 .将上述过程作适当改动后 ,可被用于平面散乱点集的三角网格化 .该通用算法除了具有快速三角化的特点之外 ,还采用局部区域的优化组合来体现最优化准则 。A general algorithm of triangulating arbitrary planar polygonal domain and scattered point set is presented. When it acts on polygonal domain, all the vertices of boundary edges and scattered points within the domain are sorted in scan manner. Each time take a feasible vertex and generate a new triangle on known edge, until the whole domain is triangulated. Swapping the diagonal of a quadrilateral is applied to locally optimize the cell form.

关 键 词：散乱点集 VORONOI图 三角化算法 凸多边形 计算机图形学 

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