-
Notifications
You must be signed in to change notification settings - Fork 0
Skeleton
Wolren edited this page Apr 30, 2026
·
3 revisions
The Skeleton family is a BCRS-free solver using medial-axis skeleton decomposition for seed generation, combined with SDF-guided boundary expansion. It offers an alternative approach to the largest inscribed rectangle problem with different computational characteristics.
Unlike BCRS which uses vertex-coordinate raster solve, Skeleton uses:
- Medial-axis skeleton decomposition for initial seed generation
- SDF (Signed Distance Field) for boundary expansion and containment verification
The approach captures the topological structure of the polygon to generate promising seed locations and orientations, then uses continuous optimization via SDF for boundary expansion.
flowchart TD
A[Stage 1: Geometry preparation] --> B[Stage 2: Skeleton extraction]
B --> C[Stage 3: Hybrid seeds - skeleton PCA + edge angles]
C --> D[Stage 4: Grid solve per seed]
D --> E[Stage 5: SDF binary expansion]
E --> F[Stage 6: Delta test (±2°)]
F --> G[Stage 7: SDF containment certification]
G --> H[Stage 8: Selection + output]
The medial axis (skeleton) of a polygon is the set of points equidistant from the polygon boundary. It encodes the topological structure as a set of connected branches.
Algorithm:
- Rasterize polygon at resolution 150 (long axis)
- Compute Euclidean distance transform
- Detect ridge points (local maxima of distance field)
- Cluster ridge points into regions using connected components
- Filter regions by clearance percentile (top 40%)
- Apply PCA to each region to extract principal orientation
Why it works:
- Points with high clearance correspond to interior "corridors" where large rectangles can fit
- The principal axis of each skeleton region indicates the optimal orientation for a rectangle in that region
- Skeleton branches naturally follow the medial structure of the polygon
The SDF provides continuous distance to the polygon boundary at any point:
SDF(p) = +distance(p, boundary) if p outside polygon
0 if p on boundary
-distance(p, boundary) if p inside polygon
Properties:
- Negative inside, positive outside, zero on boundary
- Continuous and differentiable (almost everywhere)
- Enables binary search for boundary contact without vertex discretization
Implementation:
def _polygon_sdf(poly, x, y):
pt = Point(x, y)
d_poly = poly.distance(pt)
if d_poly > 0.0:
return d_poly # outside
d_ext = poly.exterior.distance(pt)
if poly.contains(pt):
# inside: return negative distance to nearest boundary
min_d = d_ext
for ring in poly.interiors:
d_h = ring.distance(pt)
min_d = min(min_d, d_h)
return -min_d
# on boundary or in hole
return 0.0After initial grid solve, expand each rectangle side using SDF:
- For each side, compute SDF at side midpoint
- If SDF < 0 (inside), the maximum expansion is bounded by |SDF|
- Binary search from current position to maximum expansion
- Iterate 3 times for all four sides (coordinate ascent)
- 10 binary search steps per side per iteration
Advantages over CABF:
- SDF provides continuous distance estimation
- No dependency on vertex-coordinate grid
- More precise expansion bounds
SDF also enables containment verification without explicit geometric tests:
- Compute SDF at rectangle corners and midpoints
- If any point has SDF > 0 (outside), rectangle is not contained
- If contained, apply symmetric shrink (up to 20%) if needed to guarantee containment
- Validate and normalize polygon geometry
- Handle multipolygons (use largest part)
- Optional precision snapping
- Compute distance transform on rasterized polygon
- Detect ridges (local maxima of distance field)
- Cluster into regions, filter by clearance threshold
- PCA on skeleton regions → candidate angles
- Augment with nearest edge angles within ±10°
- Fall back to pure edge angles if <2 skeleton seeds
- 40×40 grid at each seed angle
- Largest-rectangle-in-histogram (LRH) algorithm
- Returns axis-aligned rectangle in rotated frame
- 10 binary search steps per side
- 3 outer iteration cycles (coordinate ascent)
- Clamp to boundary contact
- Test ±2° around each candidate angle
- Catches edge-aligned angular optima missed by skeleton PCA
- Verify full containment via SDF evaluation
- Symmetric shrink (up to 20%) if needed for certification
- Best-effort fallback if strict certification fails
- Select best certified rectangle
- Include diagnostics: rank, s2_gain, best_effort
| Parameter | Default | Purpose |
|---|---|---|
| GRID_COARSE | 40 | Initial grid resolution |
| GRID_FINE | 40 | Fine grid resolution (lower than BCRS) |
| TOP_K | 5 | Candidates for refinement |
| MAX_RATIO | 0 (unlimited) | Aspect ratio constraint |
| ALWAYS_RETURN | True | Allow fallback on failure |
| ANGLE_STEP | 5.0 | Fallback sweep step |
Benchmark on 290 real-world polygons (i5-12400F, 32GB DDR4):
| Metric | Value |
|---|---|
| Mean fill rate | 54.96% |
| Median fill rate | 52.58% |
| Min fill rate | 8.12% |
| Max fill rate | 97.52% |
| Std deviation | 21.21% |
| Time @290 | 34.64s |
Comparison with other families:
| Algorithm | Mean Fill% | Median Fill% | Time @290 (s) |
|---|---|---|---|
| Axis-Aligned | 35.87 | 35.43 | 12.98 |
| Skeleton | 54.96 | 52.58 | 34.64 |
| BCRS Fast | 55.27 | 53.24 | 15.28 |
| BCRS | 55.74 | 53.81 | 26.14 |
Best mode: 12 workers for most datasets.
-
area: Rectangle area in CRS map units -
angle_deg: Rotation angle in degrees (0-90) -
ratio: Aspect ratio (long:short) -
cand_rank: Rank of selected candidate (0 = best) -
s2_gain: Area gain from skeleton seed generation -
best_effort: 1 if fallback used, 0 otherwise
| Aspect | Skeleton | BCRS |
|---|---|---|
| Seed generation | Medial-axis skeleton (distance transform) | Edge-angle histogram |
| Expansion method | SDF binary search | CABF (vertex-coordinate clamping) |
| Containment | SDF-based evaluation | BCRS boundary-grid verification |
| Grid usage | Uniform 40×40 | Vertex-coordinate (variable pitch) |
| Mean fill rate | 54.96% | 55.74% |
| Time @290 | 34.64s | 26.14s |
Trade-offs:
- Skeleton: Different seed generation approach, slower but captures interior structure
- BCRS: Faster, slightly higher fill rate, uses vertex-coordinate grid
- SDF: Signed distance fields — Osher & Fedkiw (2003). Level Set Methods and Dynamic Implicit Surfaces.
- Medial Axis: Blum, H. (1967). "A transformation for extracting new descriptors of shape". Models for the Perception of Speech and Visual Form.
- Distance Transform: Rosenfeld, A. & Pfaltz, J.L. (1966). "Sequential operations in digital picture processing". JACM.
Navigation
- Home | Installation | Algorithms | Approximation | BCRS | Axis-Aligned | Performance | Complexity | Foundations | Parameters | Folder Layout | Usage