询问是否存在将多个小矩形合并为更少大矩形的算法

Absolutely—this is a well-studied problem in computational geometry, commonly called rectangle merging or minimum rectangle union representation. The goal is exactly what you described: take a list of axis-aligned rectangles (stored as diagonal pairs) and output the smallest possible set of rectangles that cover the exact same area.

Core Approach Breakdown #

Here’s a step-by-step, practical algorithm to achieve this:

1. Normalize All Input Rectangles #

First, ensure every rectangle is stored in a consistent format: let’s define each rectangle as (x1, y1, x2, y2) where x1 < x2 and y1 < y2 (so (x1,y1) is the bottom-left corner, (x2,y2) is the top-right). For any input rectangle where, say, x1 > x2, swap the x-values to fix it. This avoids confusion later.

2. Extract Critical Coordinates #

Pull all unique x-coordinates and y-coordinates from your input rectangles, then sort them. These coordinates act as "grid lines" that divide the plane into small, axis-aligned cells. Each cell is either completely covered by at least one input rectangle, or completely uncovered.

For your first example:

• Input rectangles: r1=(0,0,2,1), r2=(1,1,2,2), r3=(2,0,3,1)
• Unique x-coordinates (sorted): 0, 1, 2, 3
• Unique y-coordinates (sorted): 0, 1, 2

3. Mark Covered Cells #

Iterate over every small grid cell defined by the critical coordinates, and mark whether it’s covered by any input rectangle. A cell (x_start, y_start, x_end, y_end) is covered if there exists at least one input rectangle that fully contains it.

For your example, the covered cells are:

• (0,0,1,1), (1,0,2,1), (2,0,3,1) (all part of the bottom horizontal strip)
• (1,1,2,2) (the top-right small rectangle)

4. Merge Adjacent Covered Cells #

Now, merge adjacent covered cells (horizontally or vertically) into the largest possible rectangles. You can do this via:

• Connected Component Analysis: Treat each covered cell as a node, connect adjacent cells, then for each connected component, find the minimal bounding rectangle that contains all cells in the component.
• Sweep Line Technique: A more efficient method for large datasets—sort rectangle edges by x-coordinate, then track active y-intervals as you sweep from left to right, merging overlapping or adjacent intervals and generating rectangles as you go.

Example Walkthrough #

Using your first input:

• The three bottom cells are horizontally adjacent, so they merge into the single rectangle r4=(0,0,3,1).
• The top-right cell has no adjacent covered cells, so it stays as r5=(1,1,2,2).
  Which matches exactly the result you described.

Handling More Complex Cases #

Take your partial example: r1=(0,0,2,2) and r2=(0,2,1,4).

• Critical coordinates: x = 0,1,2; y = 0,2,4
• Covered cells: (0,0,1,2), (1,0,2,2), (0,2,1,4)
• Merging adjacent cells:
  • (0,0,1,2) and (0,2,1,4) are vertically adjacent, so they merge into (0,0,1,4).
  • (1,0,2,2) remains as-is.
    Result: two rectangles, which is the minimal possible.

If you added a third rectangle r3=(1,2,2,4), the covered cells would include (1,2,2,4), which merges with (1,0,2,2) vertically, and the entire set would merge into a single rectangle (0,0,2,4).

Optimization Tips #

• Preprocess Input: Remove any rectangles that are completely contained within another input rectangle—they don’t add any new coverage and just clutter the data.
• Sweep Line for Large Datasets: If you’re dealing with hundreds or thousands of rectangles, the sweep line algorithm is O(n log n) time (vs. the grid-based approach which can be O(k^2) where k is the number of critical coordinates), making it much faster.

内容的提问来源于stack exchange，提问作者Rishab Sharma