摘要
提出了一种优化的线性时间算法计算凸多边形的宽度。首先证明了凸多边形的宽度只可能介于"点边式"跨度之间,缩小了宽度的计算范围。其次提出了一种距离比较算法,降低了凸多边形跨度的计算量。最后,在"点边式"基本算法和距离比较算法的基础上,提出了计算宽度的优化算法。仿真分析表明,提出的优化算法提高了计算凸多边形宽度的效率,算法的时间复杂性降为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）.
出处
《工程图学学报》
CSCD
北大核心
2011年第2期5-9,共5页
Journal of Engineering Graphics
关键词
计算几何
优化算法
点边式
凸多边形
computational geometry
optimal algorithm
vertex-edge pairs
convex polygon
