Greedy Rectangle Merging: Turning Binary Grids into Simple Geometry – JavaScript example

Talking about Javascript.

Learn cross platform HTML5 game development

Check my Gumroad page for commented source code, games and books.

This post introduces the core idea behind greedy rectangle merging in its simplest possible form, without assuming any prior context or specific application.

At its heart, greedy rectangle merging is a grid simplification technique: given a 2D grid of cells, the goal is to describe the same information using fewer, larger geometric primitives.

The problem: too many cells

Consider a binary grid:

Each cell contains either 0 or 1.
1 means “filled”, “solid”, or “active”.
0 means “empty” or “ignored”.

Even a modest grid like 20×20 already contains 400 cells. If most of those cells are 1, treating them individually quickly becomes inefficient. Rendering, collision detection, spatial queries, or even simple iteration all suffer from unnecessary repetition.

The key observation is simple:

Large groups of adjacent 1 cells usually represent a single logical area.

Greedy rectangle merging is a way to recover that higher-level structure.

What greedy rectangle merging does

The algorithm takes a 2D array of 0 and 1 and produces a list of axis-aligned rectangles.

Each rectangle:

Covers only cells with value 1.
Never overlaps other rectangles.
Never includes cells with value 0.

Taken together, the rectangles cover exactly the same area as the original grid.

The grid representation and the rectangle representation are equivalent in meaning, but very different in cost.

Why rectangles?

Rectangles are a deliberate constraint.

Allowing arbitrary shapes would reduce the number of primitives even further, but at a significant cost:

More complex algorithms.
More expensive data structures.
Harder integration with physics and rendering systems.

Axis-aligned rectangles strike a practical balance:

Simple geometry.
Fast intersection tests.
Easy conversion to pixels, colliders, or bounding boxes.

For many real-time systems, rectangles are not a limitation — they are an advantage.

The greedy approach

The term greedy describes how the algorithm makes decisions.

Instead of searching for a globally optimal solution, it works like this:

Scan the grid from top-left to bottom-right.
When a filled cell is found, treat it as the start of a rectangle.
Rxpand the rectangle as much as possible.
Mark all covered cells as consumed.
Continue scanning.

Each decision is made using only local information. Once a rectangle is created, the algorithm never revisits that choice.

This makes greedy merging:

Fast.
Deterministic.
Easy to reason about.

The trade-off is that the result is not guaranteed to be mathematically optimal. In practice, however, it is almost always good enough.

Expansion order matters

A subtle but important detail is how the rectangle expands.

There are two natural strategies:

Horizontal-first: expand to the right, then downward.
Vertical-first: expand downward, then to the right.

Both respect the same rules, but they may produce different rectangle layouts from the same grid. Neither is universally better; each favors different spatial patterns.

This dependency on expansion order is not a bug. It is an inherent property of greedy algorithms.

Why this technique is useful

Greedy rectangle merging is widely applicable because it operates on very basic data:

Binary grids.
Boolean masks.
Occupancy maps.

Typical use cases include:

Collision maps.
Visibility masks.
Trigger areas.
Tile-based levels.
DOM or UI layouts derived from grids.

Anywhere a dense grid describes large continuous regions, greedy merging can dramatically reduce complexity.

What this technique is not

It is important to be clear about the limits:

It does not find the minimum possible number of rectangles.
It does not produce arbitrary shapes.
It does not backtrack or optimize globally.

These are conscious design choices. Greedy merging is about simplicity and performance, not theoretical optimality.

From concept to implementation

In the next step, this abstract idea can be turned into concrete code:

Start from a randomly generated binary grid
Apply greedy merging in different directions
Visualize the resulting rectangles

Only after understanding the pure algorithm does it make sense to apply it to real-world data, such as grid-based systems exported from editors like Tiled.

That progression, from abstract grid to practical application, is exactly where greedy rectangle merging shines.

Look at this example:

All three views start from the same binary grid.
Each cell is either filled (1) or empty (0), and the grid is generated randomly every time you press Regenerate.

Left: the original grid, rendered cell by cell.
Center: rectangles produced by a horizontal-first greedy merge.
Right: rectangles produced by a vertical-first greedy merge.

The input data is identical in all three cases. The only thing that changes is the order in which the greedy algorithm expands each rectangle.

This is why the two merged views often contain a different number of rectangles, even though they cover exactly the same area.

Greedy rectangle merging does not try to find a globally optimal solution. Instead, it makes local decisions, consumes cells as soon as possible, and never backtracks. This makes the algorithm fast, predictable, and easy to apply to large grids.

Pressing Regenerate simply creates a new random grid, making it easier to observe how different spatial patterns influence the result.

This is greedyMerge function, to be used with greedyMergeBest:

TypeScript

/**
	=========================================================
	GREEDY RECTANGLE MERGING
	---------------------------------------------------------
	Input:
	- a 2D grid of 0 and 1 values
	  1 = filled cell
	  0 = empty cell

	Output:
	- an array of rectangles covering all filled cells
	  rectangles are axis-aligned and non-overlapping
	=========================================================
*/

/**
	Performs greedy rectangle merging on a binary grid.
	The grid is scanned top-left to bottom-right.
	Only cells with value === 1 are merged.

	@param {number[][]} grid 2D array of 0/1 values
	@param {'horizontal-first'|'vertical-first'} mode
	@returns {{ x:number, y:number, w:number, h:number }[]}
*/
function greedyMerge(grid, mode) {

	const height = grid.length;
	const width = grid[0].length;

	/**
		Tracks which cells have already been consumed.
	*/
	const visited = new Array(height);
	for (let i = 0; i < height; i ++) {
		visited[i] = new Array(width).fill(false);
	}

	const rectangles = [];

	for (let i = 0; i < height; i ++) {
		for (let j = 0; j < width; j ++) {

			if (visited[i][j] || grid[i][j] === 0) {
				visited[i][j] = true;
				continue;
			}

			let w = 1;
			let h = 1;

			if (mode === 'horizontal-first') {

				// expand horizontally
				while (j + w < width && !visited[i][j + w] && grid[i][j + w] === 1) {
					w ++;
				}

				// expand vertically
				while (i + h < height) {
					let rowOk = true;

					for (let jj = j; jj < j + w; jj ++) {
						if (visited[i + h][jj] || grid[i + h][jj] === 0) {
							rowOk = false;
							break;
						}
					}

					if (!rowOk) {
                        break;
                    }
					h ++;
				}

			} else {

				// expand vertically
				while (i + h < height && !visited[i + h][j] && grid[i + h][j] === 1) {
					h ++;
				}

				// expand horizontally
				while (j + w < width) {
					let colOk = true;

					for (let ii = i; ii < i + h; ii ++) {
						if (visited[ii][j + w] || grid[ii][j + w] === 0) {
							colOk = false;
							break;
						}
					}

					if (!colOk) break;
					w ++;
				}
			}

			// mark rectangle as consumed
			for (let ii = i; ii < i + h; ii ++) {
				for (let jj = j; jj < j + w; jj ++) {
					visited[ii][jj] = true;
				}
			}

			rectangles.push({
				x: j,
				y: i,
				w: w,
				h: h
			});
		}
	}

	return rectangles;
}

/**
	Runs both greedy strategies and keeps the one
	that produces fewer rectangles.

	@param {number[][]} grid
	@returns {{
		rectangles: { x:number, y:number, w:number, h:number }[],
		mode: 'horizontal-first' | 'vertical-first'
	}}
*/
function greedyMergeBest(grid) {

	const h = greedyMerge(grid, 'horizontal-first');
	const v = greedyMerge(grid, 'vertical-first');

	if (v.length < h.length) {
		return { rectangles: v, mode: 'vertical-first' };
	}

	return { rectangles: h, mode: 'horizontal-first' };
}

export {
	greedyMerge,
	greedyMergeBest
};

Feel free to use it in your projects.

Never miss an update! Subscribe, and I will bother you by email only when a new game or full source code comes out.