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

An Algorithm for Solving the Minimum Circumscribed Rectangle of Curved Edges Graphs

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

In order to solve the problem of calculating the minimum circumscribed rectangle of curved edge graphs in engineering application,several existing algorithms were introduced,and their advantages and disadvantages were analyzed.A discrete iterative algorithm with time complexity of O(n)was proposed.The algorithm takes the point on the contour of a curved edge graphs as the benchmark and rotates the tangent line to get the intersection point between the tangent line and the curved edge.The tangent line passing through the intersection point was taken as a side of an external rectangle.A local minimum circumscribed rectangle is obtained in every iteration process and the required accuracy is achieved by successive iterations.The Qt program framework was used to verify the algorithm,and the feasibility and reliability of the algorithm were analyzed.The results show that the algorithm can quickly obtain the minimum circumscribed rectangle of the given curved edge graph.