| 基于简单多边形相邻凹点关系的凸剖分算法 |
| |
| 引用本文： | 董金辉,朱永芬.基于简单多边形相邻凹点关系的凸剖分算法[J].黄冈师范学院学报,2007,27(3):7-10,21. |
| |
| 作者姓名： | 董金辉 朱永芬 |
| |
| 作者单位： | 1. 黄冈师范学院,数学与信息科学学院,湖北,黄州,438000
2. 中国地质大学,计算机学院,湖北,武汉,430074 |
| |
| 摘 要： | 目的:对简单多边形的三角剖分问题中的凸剖分问题,给出一种优化的算法。方法:利用简单多边形相邻凹点连线之间的关系,对简单多边形进行分类,采用递归分解的方法,实现简单多边形的凸剖分。结果:设计的算法每次分解可以获取多个子多边形,递归分解的次数少,每次分解前求交次数方面也优于参考文献1]。结论:设计的算法简明实用,效率高,时间复杂度为O(n)。
|
| 关 键 词： | 多边形 剖分 凹点 相交 |
| 文章编号： | 1003-8078（2007）03-0007-04 |
| 修稿时间： | 2007-03-27 |
A convex decomposition algorithm of simple polygon based on its adjacent concave point connection |
| |
| DONG Jin-hui,ZHU Yong-fen.A convex decomposition algorithm of simple polygon based on its adjacent concave point connection[J].Journal of Huanggang Normal University,2007,27(3):7-10,21. |
| |
| Authors: | DONG Jin-hui ZHU Yong-fen |
| |
| Institution: | 1. College of Mathematics and Information Science, Huanggang Normal University,Huangzhou 438000,Huhei,China; 2. School of Computer Science, China University of Geosciences, Wuhan 430074, China |
| |
| Abstract: | 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,but also the algorithm becomes more efficient in decomposition than Zhou's1].Conclusion:The algorithm is simple and efficient,and has less time complexity. |
| |
| Keywords: | polygon decomposition concave point intersect |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
