关键词: 计算几何, 最狭长包络矩形, 长宽比, 飞机样板设计

Abstract: The bounding rectangle with maximum aspect ratio is a potential property of 2D
graphics. This plays important roles in applications including the intelligent design of plane
geometry, certain packing and optimum layout problems, as well as pattern recognition. However,
no previous research is known for the problem. In this paper, a solution based on the convex hull
of the given graphics is proposed to determine it. By analyzing the formulae for the maximum
aspect ratio and the rotation range of the rectangle on which four given vertexes of the polygon
are, one significant theorem is introduced and proved to show that one side of the
maximum-aspect-ratio enclosing rectangle must be collinear with an edge of the enclosed
polygon. According to this theorem, we determine the target rectangle by computing and then
comparing the aspect ratios of n bounding rectangles which respectively have a side being
collinear with different edge of the graphics’ convex hull with n edges. The experimental results
are showed to prove that the solution is both accurate and efficient.

Key words: computational geometry, bounding rectangle, aspect ratio, aircraft template
design