BCRS

BCRS Algorithms (CABF - Historical Earlier Implementation)

BCRS (Boundary-Coordinate Raster Solve) is an algorithm family in LIRiAP that combines containment certification with explicit boundary expansion (CABF). CABF (Coordinate-Ascent Boundary Fitting) was the earlier implementation approach for the "largest-area, non-axis-aligned, fully contained rectangle with expansion" target.

Note: CABF is now a historical earlier implementation. The Skeleton family provides a BCRS-free alternative using medial-axis skeleton decomposition for seed generation.

Variants

Variant	Description	Best For
Standard	Full BCRS workflow with all optimization stages	Maximum accuracy
Fast	Trial ranking + limited expensive runs	Faster with minimal accuracy loss

Algorithm Flow

flowchart TD
    A[Stage 1: Geometry preparation] --> B[Stage 2: Heuristic candidates]
    B --> C[Stage 3: Angle refinement]
    C --> D[Stage 4: BCRS boundary-coordinate solve]
    D --> E[Stage 5: CABF expansion]
    E --> F[Stage 6: Containment certification]
    F --> G{Strict certification passes?}
    G -- Yes --> H[Stage 7: Select best + output]
    G -- No --> I{Fallback enabled?}
    I -- Yes --> J[Best-effort fallback]
    I -- No --> K[No rectangle]
    J --> H

Loading

---

BCRS: Deep Dive

Key Insight

Traditional grid-based LIR solvers use uniform grid spacing. BCRS instead uses the polygon vertex coordinates themselves as grid lines. This is a key innovation because:

1. The optimal rectangle's sides are naturally aligned with polygon edges
2. At vertex coordinates, we have exact boundary positions
3. No precision loss from approximating the boundary

Boundary-Coordinate Grid

Traditional Grid:        BCRS Grid:
+------------------+    +----A----C----+
|                  |    |      |       |
|    (uniform)     |    |  B---|---D   |
|                  |    |      |       |
+------------------+    +----E----F----+

(A,C,E,F are polygon vertices that become grid lines)

Variable-Pitch LRH

Instead of fixed-width histogram bins, BCRS adapts bin widths based on the spacing of boundary coordinates. This means:

• More resolution in complex polygon regions
• Less wasted computation in simple regions
• Exact results at vertex precision

CABF Expansion

After the initial BCRS solve, Coordinate-Ascent Boundary Fitting expands each side:

1. For each rectangle side, compute the allowable expansion range
2. Use binary search to find the maximum expansion
3. Clamp to nearest vertex coordinate (not interpolate)

Clamping is critical—it prevents floating-point errors from pushing the rectangle outside containment.

---

Stage-by-Stage

Stage 1: Geometry Preparation

• Validate geometry, normalize multipolygons
• Optional precision snapping

Stage 2: Heuristic Candidates

• Edge-orientation histogram generates candidate angles
• Convex-hull upper bound prunes weak candidates
• Coarse grid search keeps top-K candidates

Stage 3: Angle Refinement

• Brent optimization refines each candidate angle
• Finds local maximum near initial guess

Stage 4: BCRS Solve

• Rotate polygon to test angle
• Build boundary-coordinate grid from vertices
• Run variable-pitch LRH solver

Stage 5: CABF Expansion

• Coordinate-ascent binary search on each side
• Clamp to nearest boundary coordinate
• Iterate until convergence

Stage 6: Containment Certification

• Verify full containment
• Controlled shrink if needed
• Best-effort fallback

Stage 7: Output

• Return best certified rectangle
• Include diagnostic fields

---

Semantics

BCRS is the only algorithm that combines:

1. Containment certification - proven inside polygon
2. Boundary expansion - rectangle touches polygon edges

This is the full target formulation for maximum-area inscribed rectangles.

---

Parameters

See Parameters for full reference.

Parameter	Purpose
GRID_COARSE	Initial grid resolution
GRID_FINE	Refinement grid resolution
TOP_K	Candidates for refinement
MAX_RATIO	Aspect ratio constraint
ALWAYS_RETURN	Allow fallback on failure

---

Performance

Variant	TOP_K	Time @290	Time @5406	Notes
Standard	3	42.35s	TBD	Full BCRS workflow
Fast	3	23.61s	445.01s	Trial ranking, ~2x faster

Best mode: Single worker (1w) — parallelization overhead exceeds per-feature computation time.

---

Output Fields

• area: Rectangle area in CRS map units
• angle_deg: Rotation angle in degrees
• ratio: Aspect ratio (long:short)
• cand_rank: Rank of selected candidate
• s2_gain: Area gain from Stage 2 (angle polishing)
• s4_gain: Area gain from Stage 4 (BCRS solve)
• s5_gain: Area gain from Stage 5 (CABF expansion)
• best_effort: 1 if fallback used

---

References

• Daniels et al. (1997): Finding the largest axis-aligned rectangle in a polygon. Proc. 13th CCCG. — Core theorem for vertex-coordinate solving.
• Bentley, J.L. (1977): Programming Pearls: Fast Algorithms for Polygon Containment. — Foundational polygon algorithms.
• Preparata, F.P. & Shamos, M.I. (1985): Computational Geometry: An Introduction. Springer. — Standard reference.

---

Navigation

• Home | Installation | Algorithms | Approximation | Skeleton | Axis-Aligned | Performance | Complexity | Foundations | Parameters | Folder Layout | Usage