Covering of polygons by rectangles

Decomposing complex patterns into standardized geometric areas is essential for many pattern recognition and CAD applications^1,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.