摘要
目的:对简单多边形的三角剖分问题中的凸剖分问题,给出一种优化的算法。方法:利用简单多边形相邻凹点连线之间的关系,对简单多边形进行分类,采用递归分解的方法,实现简单多边形的凸剖分。结果:设计的算法每次分解可以获取多个子多边形,递归分解的次数少,每次分解前求交次数方面也优于参考文献[1]。结论:设计的算法简明实用,效率高,时间复杂度为O(n)。
Objective：To present an optimum algorithm for a convex decomposition of simple polygon. Methods：Relation of its adjacent concave points and recursive decomposition. Results：The algorithm can partition the simple polygon into some convex ones, therefore, not only does the recursion reduce, hut also the algorithm becomes more efficient in decomposition than Zhou＇s [1]. Conclusion.The algorithm is simple and efficient, and has less time complexity.
出处
《黄冈师范学院学报》
2007年第3期7-10,21,共5页
Journal of Huanggang Normal University
关键词
多边形
剖分
凹点
相交
polygon
decomposition
concave point
intersect
