Determining the minimum-area encasing rectangle for an arbitrary closed curve

ABSTRACT

This paper describes a method for finding the rectangle of minimum area in which a given arbitrary plane curve can be contained. The method is of interest in certain packing and optimum layout problems. It consists of first determining the minimal-perimeter convex polygon that encloses the given curve and then selecting the rectangle of minimum area capable of containing this polygon. Three theorems are introduced to show that one side of the minimum-area rectangle must be collinear with an edge of the enclosed polygon and that the minimum-area encasing rectangle for the convex polygon is also the minimum-area rectangle for the curve.

REFERENCES

• 1: Haims, M.J., and Freeman, H. A multistage solution of the template-layout problem. IEEE Trans. Syst. Science and Cybernetics SSC-6, 2 (Apr. 1970), 145-151.
• 2: Adamowicz, M., and Albano, A. A two-stage solution of the cutting stock problem. Information Processing 71 Proc. IFIP Cong. 71, North Holland Pub. Co., Amsterdam, 1972, pp. 1086- 1091.
• 3: Eastman, C.M. Heuristic algorithms for automated space planning. Proc. 2nd lnt'l. Conf. on Artif. lntell., British Computer Society, 29 Partland Place, London, 1971, pp. 27-39.
• 4: Freeman, H. On the encoding of arbitrary geometric configurations, IRE Trans. EC-IO, 2 (June 1961), 260-268.
• 5: Freeman, H. Boundary encoding and processing. In Picture Processing and Psychopictorics, B. Lipkin and A. Rosenfeld (Eds). Academic Press, New York, 1970.
• 6: Ramer, E.U. An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing 1, 3 (Nov, 1972), 244-256.
• 7: Herbert Freeman, Computer Processing of Line-Drawing Images, ACM Computing Surveys (CSUR), v.6 n.1, p.57-97, March 1974 [doi>10.1145/356625.356627]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Performance, Theory

Keywords:
enclosed curve, minimum-area encasing rectangle, optimum layout, optimum packing