基于凹凸顶点判定的简单多边形Delaunay三角剖分.pdfVIP

第 1 1 卷　第 1 期 计算机辅助设计与图形学学报 V o l. 11,N o. 1 1999 年 1 月 JOU RN AL O F COM PU T ER A ID ED D E S IGN AN D COM PU T ER GRA PH IC S J an. , 1999 基于凹凸顶点判定的 简单多边形D elaunay 三角剖分 马小虎 潘志庚　石教英 　 (徐州师范大学计算机科学系　徐州　22 1009) (浙江大学CAD CG 国家重点实验室　杭州　3 10027) 摘　要　提出一种基于凹凸顶点判定的简单多边形D e laun ay 三角剖分算法. 该算法首先求出简单多边形的凹凸顶 点, 然后, 逐次割去一个权值最大的三角形构造三角形网格, 修改多边形顶点链表, 并重新计算受影响的顶点的凹凸 性. 重复这个过程, 直到边界顶点链表空为止. 关键词　多边形, 链表, 凹凸顶点, D e laun ay 三角剖分, 细节层次 中图法分类号　T P 39 1 D ELA UNAY TR IA NGULA T IO N O F SIM PL E POLY GO N BA SED O N - D ETERM INA T IO N O F CO NVEX CO NCA VE VERT ICES M A X iao H u ( , , 　22 1009) D ep a r tm en t of Comp u ter S cience X uz hou N orm a l U n iv ers ity X uz hou 　 PAN Zh i Gen g SH I J iao Y in g (S ta te K ey L abora tory of CA D CG , Z hej iang U n iv ers ity , H ang z hou　3 10027) Abstract　　T h is p ap er p re sen t s a fa st a lgo r ithm fo r D e laun ay t r iangu lat ion o f sim p le po lygon b a sed on determ in at ion . , o f convex con cave ver t ice s It s b a sic idea is to ca lcu late convex con