Covering of polygons by rectangles

F. Cheng, I. M. Lin

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Decomposing complex patterns into standardized geometric areas is essential for many pattern recognition and CAD applications1,2. The decomposition of polygons into rectangles is studied in the paper. An algorithm that covers convex polygons by rectangles is presented. The algorithm works in two stages: interior covering and boundary covering. For a given convex polygon, the algorithm covers the interior of the polygon by a few rectangles first, then covers the remaining areas by rectangles constructed along the edges of the polygon. No searching for uncovered areas is required. The performance of this algorithm is extremely efficient. It takes only one seventh of the time required by a previous algorithm to cover a convex polygon with about the same number of rectangles.

Original languageEnglish
Pages (from-to)97-101
Number of pages5
JournalCAD Computer Aided Design
Issue number2
StatePublished - Mar 1989


  • geometry
  • pattern recognition
  • polygon decomposition

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Covering of polygons by rectangles'. Together they form a unique fingerprint.

Cite this