一个求解多边形最小面积外接矩形的算法

An Algorithm for Computing the Minimum Area Bounding Rectangle of an Arbitrary Polygon

多边形最小面积外接矩形是地理信息系统和图形学领域一个极其有用的工具,但是其精确求解过程比较困难。首先证明了一个多边形的最小面积外接矩形必定过该多边形凸包的一条边,然后基于该思想提出了一个计算多边形最小面积外接矩形的算法,并对算法的效率进行了分析。最后给出了算法的实验算例,进一步说明了算法的可行性与可靠性。

The minimum area bounding rectangle （MABR） of an arbitrary polygon is an important tool in the geographic information systems and computer graphics, but how to precisely calculate it is of great difficulty. Firstly, the MABR of an arbitrary polygon shares a common edge with the convex hull of the polygon is proved. Secondly, an algorithm for computing MABR based on this idea is presented and the efficiency of the algorithm is discussed. Finally, some experiments are given to show the feasibility and reliability of the algorithm.