Introduction

A rectilinear polygon has only horizontal and vertical edges, which makes rectangle decomposition possible in a very natural way. The important question is whether you need any valid rectangle partition or the minimum possible number of rectangles, because those are different problems.

Partition Versus Optimal Partition

If you only need a valid tiling, the problem is approachable with scanline or grid-based methods. If you need the fewest rectangles, the problem becomes a more serious computational-geometry task.

In practical software, many applications are satisfied with a correct partition rather than a mathematically minimal one. Examples include layout engines, collision preprocessing, and map tiling.

A Simple Grid-Based Approach

For integer-coordinate rectilinear polygons, one practical method is:

• represent the polygon as unit cells on a grid
• mark which cells lie inside the shape
• greedily merge adjacent cells into maximal rectangles

This is not always optimal in rectangle count, but it is easy to implement and produces a valid tiling.

Here is a runnable Python example using occupied unit cells.

1def decompose(cells):
2    cells = set(cells)
3    rectangles = []
4
5    while cells:
6        x0, y0 = min(cells)
7
8        width = 1
9        while (x0 + width, y0) in cells:
10            width += 1
11
12        height = 1
13        growing = True
14        while growing:
15            for dx in range(width):
16                if (x0 + dx, y0 + height) not in cells:
17                    growing = False
18                    break
19            if growing:
20                height += 1
21
22        rect = (x0, y0, width, height)
23        rectangles.append(rect)
24
25        for dx in range(width):
26            for dy in range(height):
27                cells.remove((x0 + dx, y0 + dy))
28
29    return rectangles
30
31l_shape = {
32    (0, 0), (1, 0), (2, 0),
33    (0, 1),
34    (0, 2)
35}
36
37print(decompose(l_shape))

For the simple L shape above, the algorithm returns a set of non-overlapping rectangles that exactly cover the region.

Why the Greedy Strategy Works for Valid Coverage

Each step chooses one remaining cell and expands a maximal axis-aligned rectangle over still-uncovered cells. Because every removed cell belongs to exactly one rectangle, the final set is a partition.

The method is easy to reason about and often good enough for discrete geometry problems.

What it does not guarantee is minimum rectangle count. A different choice of the first rectangle can lead to fewer total rectangles later.

Continuous Polygons Need Preprocessing

If your input is a polygon boundary rather than a list of unit cells, the usual workflow is:

• extract all unique x coordinates from vertical edges
• extract all unique y coordinates from horizontal edges
• form the induced rectangular grid
• test which small grid cells lie inside the polygon
• merge adjacent interior cells

This coordinate-compression trick converts the continuous polygon into a finite grid while preserving every boundary change.

It is a standard way to turn geometric decomposition into a combinatorial problem.

When Minimum Rectangle Count Matters

If the objective is the minimum number of rectangles, greedy merging is no longer enough. More advanced algorithms analyze concave vertices, admissible cuts, and structural properties of rectilinear polygons.

For many engineering tasks, a near-minimal or just-valid partition is acceptable. For VLSI, CAD, or theoretical optimization, exact minimum decomposition may be worth the extra complexity.

That distinction should be decided before implementation. Many teams spend time chasing optimality when the product requirement only needs a correct cover.

Edge Cases to Handle

A robust implementation must define whether:

• touching at an edge is allowed
• polygons may contain holes
• coordinates are integer or floating-point
• the output rectangles must align to an input grid

Holes are especially important. A polygon with holes cannot be treated as one simply connected filled area unless the hole boundaries are represented and excluded explicitly.

Common Pitfalls

The biggest mistake is assuming every greedy rectangle choice yields the minimum rectangle count. It does not.

Another mistake is forgetting to distinguish between covering and partitioning. A cover may overlap; a partition may not.

A third issue is trying to operate directly on floating-point boundaries without coordinate normalization. Small numeric inconsistencies can break adjacency checks.

Finally, if the polygon has holes, an algorithm written for simple rectilinear polygons may silently fill the hole unless that case is handled explicitly.

Summary

• Rectilinear polygons can be partitioned into axis-aligned rectangles because all edges are horizontal or vertical.
• A grid-based greedy merge is a practical way to obtain a valid rectangle decomposition.
• Valid decomposition is easier than minimum-rectangle decomposition.
• Coordinate compression helps convert boundary geometry into mergeable cells.
• Decide early whether you need any valid partition or the optimal one.
• Handle holes, numeric precision, and non-overlap requirements explicitly.