Introduction

Fitting a rectangle inside a polygon sounds simple until you ask what exactly should be optimized. The problem changes a lot depending on whether the rectangle must be axis-aligned or may rotate, and whether you want an exact maximum-area answer or a practical approximation.

Clarify the Problem Variant First

There are several different versions of the problem:

• largest axis-aligned rectangle inside a polygon
• largest rotated rectangle inside a polygon
• rectangle maximizing area
• rectangle maximizing width under a height constraint, or the reverse

Those are not equivalent. An exact algorithm for one variant does not automatically solve the others.

In practice, a lot of engineering work uses approximate optimization rather than a mathematically exact global optimum for arbitrary polygons.

The Axis-Aligned Case Is Easier

If the rectangle must remain axis-aligned, the search space is smaller. A practical strategy is:

1. choose candidate x intervals
2. choose candidate y intervals
3. form a rectangle from them
4. test whether the rectangle is fully inside the polygon
5. keep the best one

That can be accelerated with geometry libraries or sampling strategies, but the key simplification is that the rectangle orientation is fixed.

For a coarse approximation, sampling candidate corners on a grid can work surprisingly well.

The Rotated Case Is Harder

If the rectangle may rotate, the search now includes:

• center position
• width
• height
• angle

That makes the continuous search much harder. A practical algorithm usually does one of these:

• sample candidate angles and solve an axis-aligned subproblem after rotation
• use numerical optimization
• use random search or simulated annealing
• use a geometry library to validate candidate rectangles

The most common engineering approach is to rotate the polygon by candidate angles and look for large axis-aligned rectangles in the rotated coordinate system.

A Practical Search Strategy

A good approximate algorithm for the rotated case is:

1. sample a set of candidate angles
2. rotate the polygon by each angle
3. search for a large axis-aligned rectangle in that rotated frame
4. rotate the winning rectangle back
5. keep the best area found

This works because a rotated rectangle in the original polygon becomes an axis-aligned rectangle after rotating the coordinate system.

The main cost is the search over angles and candidate positions.

Using Shapely for a Search-Based Approach

If you only need a practical solution, a search loop with a geometry library can be simpler than deriving a closed-form algorithm from scratch.

1from shapely.geometry import Polygon, box
2from shapely import affinity
3
4polygon = Polygon([
5    (0, 0), (8, 0), (9, 3), (6, 7), (1, 6)
6])
7
8
9def fits(poly, center_x, center_y, width, height, angle_deg):
10    rect = box(-width / 2, -height / 2, width / 2, height / 2)
11    rect = affinity.rotate(rect, angle_deg, origin=(0, 0))
12    rect = affinity.translate(rect, center_x, center_y)
13    return poly.covers(rect), rect

Then search over candidate positions and sizes:

1best_area = 0
2best_rect = None
3
4for angle in range(0, 180, 5):
5    for x in [i / 2 for i in range(0, 20)]:
6        for y in [i / 2 for i in range(0, 20)]:
7            for w in [i / 2 for i in range(1, 20)]:
8                for h in [i / 2 for i in range(1, 20)]:
9                    ok, rect = fits(polygon, x, y, w, h, angle)
10                    if ok and w * h > best_area:
11                        best_area = w * h
12                        best_rect = rect
13
14print(best_area)

This is not an exact solver, but it is conceptually simple and often good enough as a baseline.

Make the Search Smarter

A naive brute-force search gets expensive quickly. Practical improvements include:

• sample centers only inside the polygon's bounding box
• use binary search on width or height once an angle and center are chosen
• sample candidate angles from polygon edge directions instead of every possible angle
• start coarse and refine near the best candidate

These ideas preserve the search-based design while making it usable on more realistic polygons.

Containment Testing Matters

A rectangle is valid only if the whole shape lies inside the polygon, not just its center. That means you should test the rectangle polygon itself against the original polygon using a containment predicate such as covers or contains, depending on whether touching the boundary is allowed.

That distinction matters. Some applications accept a rectangle on the border. Others require strict interior placement.

Exact Algorithms Versus Practical Algorithms

For convex polygons, there are more specialized geometric methods. For arbitrary concave polygons, exact maximum-area inscribed rectangle algorithms exist in the research literature, but they are usually much more complex than what many application developers need.

So the right engineering answer is often:

• if the polygon is simple and performance matters, use a specialized method
• if the polygon is arbitrary and a very good approximation is enough, use a search-based approach

That tradeoff is often more important than whether the solution is mathematically elegant.

Common Pitfalls

One common mistake is not defining whether the rectangle may rotate. That single decision changes the problem dramatically.

Another pitfall is testing only the rectangle center instead of testing the entire rectangle for containment.

A third issue is assuming that a method for a convex polygon automatically works well for a concave polygon.

Finally, brute-force search can become intractable quickly if you search too many positions, sizes, and angles without pruning or refinement.

Summary

• Fitting a rectangle inside a polygon is several different problems depending on orientation and objective.
• Axis-aligned versions are easier than freely rotated versions.
• A practical rotated-rectangle method is to sample angles and solve an axis-aligned subproblem in rotated coordinates.
• Search-based methods with geometry libraries are often the most realistic engineering solution.
• Always validate full-rectangle containment, not just the rectangle center.