-
Notifications
You must be signed in to change notification settings - Fork 0
Foundations
Background on the Largest Inscribed Rectangle problem and the geometric principles underlying LIRiAP algorithms.
Given a simple polygon P (possibly with holes), find the rectangle R of maximum area such that R is strictly contained in P. The rectangle may be rotated (non-axis-aligned).
- Axis-aligned: Rectangle sides parallel to coordinate axes
- Rotated: Rectangle may have any orientation
- With constraints: Maximum aspect ratio, minimum area, etc.
For axis-aligned rectangles, Daniels et al. (1997) proved that the optimal rectangle always has at least two sides determined by vertex coordinates of the polygon. This enables efficient exact solvers using vertex-coordinate grids.
The general (rotated) case is NP-hard to solve exactly. Approaches include:
- Heuristic search over orientation space
- Grid-based approximation
- Boundary-coordinate raster methods (BCRS)
The classic stack-based algorithm for finding the largest rectangle in a histogram. Runs in O(n) time.
Reference: Klingel, E. (1986). Finding the largest rectangle in a polygon. Algorithmica.
For convex polygons, the optimal axis-aligned rectangle has its top and bottom edges tangent at polygon vertices. This enables O(n²) exact solving via vertex-pair enumeration.
References:
- Alt, H., Hagerup, T., Mehlhorn, K., Preparata, F.P. (1987). Deterministic simulation of idealized parallel computers. Information and Computation.
- Amenta, N. (1994). A short proof of an interesting heuristic result. Proc. 5th ACM-SIAM SODA.
Core Theorem: The largest axis-aligned rectangle in a simple polygon always has at least two sides determined by vertex x- or y-coordinates. This is the foundation for the exact axis-aligned solvers.
Reference: Daniels, K., Milenkovic, V., Roth, D. (1997). Finding the largest axis-aligned rectangle in a polygon. Proc. 13th Canadian Conf. Computational Geometry.
Bounded scalar optimization for angle refinement. Used for local search around candidate orientations.
Reference: Brent, R.P. (1973). Algorithms for Finding Zeros and Extrema of Functions Without Calculating Derivatives. Prentice-Hall.
References:
- [1] Bentley, J.L. (1977). Programming Pearls: Fast Algorithms for Polygon Containment. Communications of the ACM, 20(11), 887-891. https://dl.acm.org/doi/10.1145/1283920.3283334
- [2] Preparata, F.P., & Shamos, M.I. (1985). Computational Geometry: An Introduction. Springer-Verlag.
1. Extract all vertex x-coordinates from polygon exterior
2. Extract all vertex x-coordinates from each interior ring
3. Add minx and maxx to the set
4. Remove duplicates → X = sorted unique x values [x0, x1, ..., xm]
5. Repeat for y-coordinates → Y = [y0, y1, ..., yn]
6. Grid has (m) columns × (n) rows
If len(X) > 300 or len(Y) > 300: abort BCRS, use uniform grid seed.
For each cell [Xi, Xi+1] × [Yj, Yj+1]:
center = ((Xi + Xi+1)/2, (Yj + Yj+1)/2)
if polygon.contains(center):
mask[j][i] = 1
else:
mask[j][i] = 0
For row j:
heights[i] = cumulative sum of mask[j][i] for all i above
For each column i:
Pop from stack while top.height > current.height
For each popped span [start, end]:
width = X[end+1] - X[start]
height = j - (j - popped.height + 1) = popped.height
depth = Y[j+1] - Y[j - height + 1]
area = width × depth
update best
Push current column to stack
Width uses X[end+1] - X[start] (variable pitch), not uniform Δx.
Daniels et al. (1997) proved: the largest axis-aligned rectangle in a simple polygon has at least two sides aligned with vertex x- or y-coordinates.
Therefore: searching the vertex-coordinate grid finds the global optimum.
SDF(point) returns:
- positive distance if point outside polygon
- 0 if point on boundary
- negative distance if point inside (distance to nearest boundary)
Implementation:
d = polygon.distance(point)
if d > 0: return d
if polygon.contains(point):
return -min(polygon.exterior.distance(point),
min(hole.distance(point) for hole in polygon.interiors))
return 0
For rectangle side at x = x0:
1. Compute SDF at side midpoint: s = SDF(x0, (y0+y1)/2)
2. If s < 0 (inside):
d_max = min(x0 - minx, abs(s))
Else:
d_max = x0 - minx
The bound abs(s) uses actual distance to boundary, not vertex-coordinate gap.
d = 0
for step in 1 to 10:
mid = (d + d_max) / 2
if polygon.covers(box(x0 - mid, y0, x1, y1)):
d = mid
else:
d_max = mid
Repeat for right, bottom, top. Run 3 iterations (coordinate ascent).
SDF_max = -infinity
For each of 4 corners:
SDF_max = max(SDF_max, SDF(corner))
For each of 4 edge midpoints:
SDF_max = max(SDF_max, SDF(midpoint))
Eight queries total, O(1) with respect to polygon size.
If SDF_max <= epsilon (1e-7):
Rectangle is contained
Else:
shrink = SDF_max + 2*epsilon
If shrink > 0.20 × min(half_width, half_height):
Reject
Else:
Reduce dimensions by shrink
Re-verify SDF_max <= epsilon
If passes: return shrunk rectangle
Else: reject
The shrink guarantees containment by moving all points inward by at least |SDF_max|.
- Heuristic edge-direction analysis
- Grid-based search with refinement
- No containment guarantee
- Medial-axis skeleton decomposition for seed generation
- SDF-guided boundary expansion
- BCRS-free alternative
- Best-effort fallback when strict fails
- Boundary-coordinate raster solve (BCRS)
- Uses polygon vertex coordinates as grid lines
- SDF-guided boundary expansion
- Novel contributions in variable-pitch LRH and coordinate-ascent fitting
- Exact solvers for fixed-orientation
- Alt/Amenta for convex polygons
- Daniels et al. vertex-grid for general polygons
- Vertex-coordinate precision
- Low vertex count (<100): Exact methods feasible
- Medium vertex count (100-1000): Grid-based methods appropriate
- High vertex count (>1000): Need downsampling or approximation
- Approximation: No guarantee
- Skeleton: Strict when certification passes
- BCRS: Strict when certification passes
- Axis-Aligned: Exact (vertex-coordinate precision)
- Speed vs. accuracy
- Strictness vs. always-return
- Single-threaded vs. parallel
Navigation
- Home | Installation | Algorithms | Approximation | Skeleton | BCRS | Axis-Aligned | Performance | Complexity | Parameters | Folder Layout | Usage