| 简单多边形分解成凸多边形差组合的算法 |
| |
| 引用本文： | 汪嘉业,汪卫.简单多边形分解成凸多边形差组合的算法[J].计算机辅助设计与图形学学报,1992,4(2):22-29. |
| |
| 作者姓名： | 汪嘉业 汪卫 |
| |
| 作者单位： | 浙江大学CAD&CG国家重点实验室，山东大学计算机系 杭州 310027，济南 250100 |
| |
| 摘 要： | 本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N~2),其中N为原多边形的边数。
|
| 关 键 词： | 分解 算法 凸多边形 差组合 多边形 |
Algorithm for Finding Convex Decomposition of Simple Polygons |
| |
| Wang Jiaye and Wang WeiShandong University,Jinan, State Key Lab. of CAD & CG,Zhejiang University,Hangzhou.Algorithm for Finding Convex Decomposition of Simple Polygons[J].Journal of Computer-Aided Design & Computer Graphics,1992,4(2):22-29. |
| |
| Authors: | Wang Jiaye and Wang WeiShandong University Jinan State Key Lab of CAD & CG Zhejiang University Hangzhou |
| |
| Affiliation: | Wang Jiaye and Wang WeiShandong University,Jinan,250100 State Key Lab. of CAD & CG,Zhejiang University,Hangzhou,310027 |
| |
| Abstract: | An Algorithm for finding convex decomposition of simple polygons is described. This algorithm finds the convex hull of a simple polygon and then recurses to find the convex hull of the original region and itsconvex hull until such regions are convex. The time complexity of the algorithm is proved to be O(n2) , where N is the number of edges of the original polygon. |
| |
| Keywords: | simple polygons convex hull time complexity |
| 本文献已被 CNKI 维普 等数据库收录！ |
