Introduction

Placing a rectangle inside a polygon sounds simple until you ask what "best" means. The problem changes depending on whether the rectangle must be axis-aligned or may rotate, whether you want any feasible placement or the maximum-area placement, and whether the polygon is convex or concave.

Start by Fixing the Problem Statement

The title question is too broad unless you choose a specific version. A practical version is:

"Find a large axis-aligned rectangle completely inside a simple polygon."

That version is easier to reason about than the fully general "largest arbitrary rotated rectangle inside any polygon." The fully general problem needs more advanced geometry and optimization machinery.

For the axis-aligned version, a common engineering approach is:

1. generate candidate rectangle positions
2. test whether each rectangle is fully inside the polygon
3. keep the best feasible rectangle found

This does not guarantee the true optimum unless your candidate set is exhaustive, but it is practical and easy to implement.

Geometry You Need

Two checks matter:

• each rectangle corner must lie inside the polygon
• each rectangle edge must stay inside and not cross polygon edges

For convex polygons, checking corners is often enough. For concave polygons, corner-only checks can fail because an edge of the rectangle may pass through a notch in the polygon even when all four corners lie inside.

That is why a robust implementation needs edge intersection tests too.

A Simple Search Heuristic in Python

The following runnable example uses:

• ray casting for point-in-polygon
• segment intersection tests
• a coarse grid over the polygon bounding box

It searches for a large axis-aligned rectangle. It is a heuristic, not a mathematically perfect optimizer, but it demonstrates the algorithm clearly.

1from itertools import combinations
2
3
4def point_in_polygon(x, y, polygon):
5    inside = False
6    n = len(polygon)
7    for i in range(n):
8        x1, y1 = polygon[i]
9        x2, y2 = polygon[(i + 1) % n]
10        if ((y1 > y) != (y2 > y)):
11            x_intersection = (x2 - x1) * (y - y1) / (y2 - y1) + x1
12            if x < x_intersection:
13                inside = not inside
14    return inside
15
16
17def ccw(a, b, c):
18    return (c[1] - a[1]) * (b[0] - a[0]) > (b[1] - a[1]) * (c[0] - a[0])
19
20
21def segments_intersect(a, b, c, d):
22    return ccw(a, c, d) != ccw(b, c, d) and ccw(a, b, c) != ccw(a, b, d)
23
24
25def rectangle_inside_polygon(rect, polygon):
26    x1, y1, x2, y2 = rect
27    corners = [(x1, y1), (x2, y1), (x2, y2), (x1, y2)]
28    edges = list(zip(corners, corners[1:] + corners[:1]))
29    poly_edges = list(zip(polygon, polygon[1:] + polygon[:1]))
30
31    if not all(point_in_polygon(x, y, polygon) for x, y in corners):
32        return False
33
34    for e1 in edges:
35        for e2 in poly_edges:
36            if segments_intersect(e1[0], e1[1], e2[0], e2[1]):
37                return False
38    return True
39
40
41def search_large_rectangle(polygon, step=1.0):
42    xs = [p[0] for p in polygon]
43    ys = [p[1] for p in polygon]
44    min_x, max_x = int(min(xs)), int(max(xs))
45    min_y, max_y = int(min(ys)), int(max(ys))
46
47    best = None
48    best_area = -1
49
50    x_values = [min_x + i * step for i in range(int((max_x - min_x) / step) + 1)]
51    y_values = [min_y + i * step for i in range(int((max_y - min_y) / step) + 1)]
52
53    for x1, x2 in combinations(x_values, 2):
54        for y1, y2 in combinations(y_values, 2):
55            rect = (x1, y1, x2, y2)
56            area = (x2 - x1) * (y2 - y1)
57            if area > best_area and rectangle_inside_polygon(rect, polygon):
58                best = rect
59                best_area = area
60
61    return best, best_area
62
63
64polygon = [(0, 0), (8, 0), (8, 5), (5, 5), (5, 3), (0, 3)]
65rect, area = search_large_rectangle(polygon, step=1.0)
66print(rect, area)

This code is deliberately simple. For small polygons and coarse grids it is fine. For large inputs or high precision, it becomes expensive quickly.

Improving the Search

Once the basic version works, there are several ways to improve it.

First, use candidate x and y coordinates derived from polygon vertices and edge intersections instead of a uniform grid. That reduces wasted search points.

Second, use binary search on width or height once a feasible anchor is found. That can replace many brute-force rectangle checks.

Third, separate the convex and concave cases. Convex polygons support stronger geometric shortcuts, while concave polygons need more careful feasibility checks.

If rotation is allowed, the problem becomes richer. A practical strategy there is:

1. sample a set of candidate rotation angles
2. rotate the polygon oppositely
3. solve the axis-aligned problem in the rotated frame

That still remains approximate, but it is often good enough for engineering tasks.

Common Pitfalls

The biggest mistake is checking only the rectangle corners for a concave polygon. That can accept rectangles whose edges cross outside the polygon boundary.

Another issue is pretending a coarse grid gives the exact optimum. It only gives the best rectangle among the positions you sampled.

Degenerate cases also matter. Rectangles touching the boundary, polygons with collinear edges, and floating-point precision can all affect feasibility tests.

Finally, always specify whether the rectangle may rotate. Without that detail, two people can solve different problems and both claim to be correct.

Summary

• Rectangle placement inside a polygon must be defined precisely before choosing an algorithm.
• For axis-aligned rectangles, a candidate-search plus feasibility-test approach is practical.
• Concave polygons require more than corner checks; edge intersection tests matter.
• Coarse grid search is easy to implement but only approximate.
• Allowing rotation turns the problem into a harder optimization task.