一种求解graph的最小外接矩形的算法

作者:王秋娇; 秦春桃; 帅玉琳
来源:成都工业学院学报, 2019, 22(01): 41-44.
DOI:10.13542/j.cnki.51-1747/tn.2019.01.010

摘要

为解决工程应用中曲边图形的最小外接矩形的计算问题,介绍了现有的几种算法,分析了其优缺点。提出一种时间复杂度为O(n)的离散迭代算法,该算法以曲边图形轮廓上的一点为基准,旋转切线获得切线与曲边轮廓的交点,以过该交点的切线为一条边作外接矩形。每次迭代得到局部最小外接矩形,逐次迭代达到所要求的精度。使用Qt程序框架验证了该算法,分析了该算法的可行性和可靠性。结果表明,该算法可以快速高效地获得给定曲边图形的最小外接矩形。

全文