摘要
提出一种确定任意多边形凸凹顶点的快速算法，该算法的时间复杂性为Ｏ（ｎ）次乘法和Ｏ（ｎ）次比较。还介绍把该算法用于求平面点集的凸包以及对任意的平面多边形进行Ｄｅｌａｕｎａｙ三角剖分。
This paper presents a fast algorithm for determining convex-concave vertices of an arbitray polygon. The algorithm requires O(n) multiplications and O(n) comparisions. Some applications of the algorithm are also discussed in the paper.
出处
《计算机工程与设计》
CSCD
北大核心
1998年第3期45-49,共5页
Computer Engineering and Design
关键词
多边形
凸包
快速算法
CAD
Polygons Convex hull Delaunay triangulation
