| 一种求凸多边形宽度的优化算法 |
| |
| 引用本文： | 陈海,王新民,焦裕松,李俨. 一种求凸多边形宽度的优化算法[J]. 工程图学学报, 2011, 32(2): 5-9 |
| |
| 作者姓名： | 陈海 王新民 焦裕松 李俨 |
| |
| 作者单位： | 西北工业大学自动化学院; |
| |
| 摘 要： | 提出了一种优化的线性时间算法计算凸多边形的宽度。首先证明了凸多边形的宽度只可能介于＂点边式＂跨度之间,缩小了宽度的计算范围。其次提出了一种距离比较算法,降低了凸多边形跨度的计算量。最后,在＂点边式＂基本算法和距离比较算法的基础上,提出了计算宽度的优化算法。仿真分析表明,提出的优化算法提高了计算凸多边形宽度的效率,算法的时间复杂性降为O（n）。
|
| 关 键 词： | 计算几何 优化算法 点边式 凸多边形 |
An Optimal Algorithm for Calculating the Width of Convex Polygons |
| |
| CHEN Hai,WANG Xin-min,JIAO Yu-song,LI Yan. An Optimal Algorithm for Calculating the Width of Convex Polygons[J]. Journal of Engineering Graphics, 2011, 32(2): 5-9 |
| |
| Authors: | CHEN Hai WANG Xin-min JIAO Yu-song LI Yan |
| |
| Affiliation: | CHEN Hai,WANG Xin-min,JIAO Yu-song,LI Yan (College of Automation,Northwestern Polytechnical University,Xi'an Shaanxi 710072,China) |
| |
| Abstract: | An optimal linear time algorithm is proposed to calculate the width of convex polygons.It is proved that the width of a convex polygon only be found between the span of vertex-edge pairs.In this way,the range of calculation narrows down.Then an algorithm using distance comparison is investigated to reduce the calculation of the span.Based on the basic algorithm of vertex-edge pairs and the distance comparison,the optimal algorithm for calculating the width is proposed.The simulation results show that the pr... |
| |
| Keywords: | computational geometry optimal algorithm vertex-edge pairs convex polygon |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
