一种解算空间几何对象的最小外接矩形算法

An Algorithm for Computing the Smallest-Area Enclosing Rectangle of Spatial Geometric Object(s)

提出并实现了一种解算点群、线群以及面群最小外接矩形的新算法。首先将求解点群、线群以及面群的最小外接矩形问题全部转化为求解构成这些几何对象的边界点集合凸壳的最小外接矩形问题;其次,在算法中采用几何计算方法直接得到矩形的4个顶点坐标,避免了大量旋转角度计算和坐标变换运算,从而降低了算法的计算量,提高了算法的精确度。最后通过实例验证了该算法的可行性。

In this paper, a new algorithm is given for computing the smallest-area enclosing rectangle of points, lines and polygons. First, the problem of calculating the smallest-area enclosing rectangle for points, lines and polygons is converted to the problem of computing the smallest-area enclosing rectangle for their convex hull. Secondly, the four points of the rectangle for a convex hull are computed by geometric computa tion. The computation of many angles of rotation and coordina improve the precision. Finally, the new algorithm is verified te transformations is avoided in order to with some examples.