一种求凸多边形宽度的优化算法  

An Optimal Algorithm for Calculating the Width of Convex Polygons

作　　者：陈海[1] 王新民[1] 焦裕松[1] 李俨[1] 

机构地区：[1]西北工业大学自动化学院,陕西西安710072

出　　处：《工程图学学报》2011年第2期5-9,共5页Journal of Engineering Graphics

摘　　要：提出了一种优化的线性时间算法计算凸多边形的宽度。首先证明了凸多边形的宽度只可能介于"点边式"跨度之间,缩小了宽度的计算范围。其次提出了一种距离比较算法,降低了凸多边形跨度的计算量。最后,在"点边式"基本算法和距离比较算法的基础上,提出了计算宽度的优化算法。仿真分析表明,提出的优化算法提高了计算凸多边形宽度的效率,算法的时间复杂性降为O(n)。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 proposed algorithm greatly improves the efficiency of caculating the width of convex polygons,and reduces the time complexity to O（n）.

关 键 词：计算几何 优化算法 点边式 凸多边形 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]