-
Notifications
You must be signed in to change notification settings - Fork 0
Skeleton
Skeleton uses medial-axis skeleton decomposition to generate seed orientations, combined with SDF-guided expansion and SDF-based certification. BCRS-free alternative.
- Validate polygon: check
is_validandis_empty - If multipart: use largest component by area
- Extract bounds:
minx, miny, maxx, maxy - Compute aspect ratio:
h / w(long axis / short axis)
Long axis resolution: 150
Short axis resolution: max(3, int(150 × aspect))
If h > w: swap dimensions
Create dense grid covering polygon bounds
For each grid cell inside polygon:
Compute Euclidean distance to nearest boundary point
Store in dist[y][x] array
This yields a distance field where interior points farther from boundary have higher values.
For each cell:
If dist[y][x] > 0 and dist[y][x] >= local_max(3×3 neighborhood) - epsilon:
Mark as ridge point
Ridge points are local maxima of the distance field. They form the medial axis (skeleton) [1].
Apply connected components labeling to ridge points
Each connected cluster = one skeleton region
Discard regions with < 5 pixels
For each region:
Compute clearance = max(dist values in region)
Collect all region clearances
threshold = 60th percentile of clearances
Keep only regions with clearance >= threshold
This keeps regions with high clearance (wide corridors).
For each kept region:
Extract all (x, y) coordinates
Compute mean-centered coordinates
Compute 2×2 covariance matrix
Compute eigenvalues and eigenvectors
Principal orientation = eigenvector for largest eigenvalue
Convert to angle ∈ [0°, 90°]
The principal axis gives the optimal rectangle orientation for that region.
For each skeleton region (max 5 by default):
Store: (center_x, center_y, angle, max_clearance, total_clearance, pixel_count)
Compute score = clearance × clearance × total_clearance
Sort by score descending
Apply spatial filtering: discard seeds within 0.5 × clearance of earlier kept seed
Extract all unique edge orientations from polygon exterior
Modulo 90° to handle symmetry
Include 0° and 45° if not present
For each skeleton seed:
Find 2 nearest edge angles within ±10°
Add as fallback seeds
If < 2 skeleton seeds after filtering:
Use pure edge-angle candidates instead
For each seed angle θ:
1. Rotate polygon by -θ around centroid
2. Run uniform grid LRH (40×40):
- Build mask at grid resolution
- Stack-based LRH for largest rectangle
- Return axis-aligned rectangle in rotated frame
3. Return rectangle bounds [x0, x1] × [y0, y1]
For each seed's rectangle, apply expansion (same as BCRS Stage 5):
SDF(point):
d = polygon.distance(point)
if d > 0: return d // outside, positive
d_ext = polygon.exterior.distance(point)
if polygon.contains(point):
min_d = d_ext
for hole in polygon.interiors:
min_d = min(min_d, hole.distance(point))
return -min_d // inside, negative
return 0 // on boundary or in hole
For left side (x0):
1. Query midpoint: s = SDF(x0, (y0+y1)/2)
2. Upper bound:
If s < 0: d_max = min(x0 - minx, abs(s))
Else: d_max = x0 - minx
3. Binary search (10 steps):
lo = 0, hi = d_max
while lo < hi:
mid = (lo + hi) / 2
if covers(polygon, box(x0-mid, y0, x1, y1)):
lo = mid
else:
hi = mid
d_left = lo
Repeat for right, bottom, top. Run 3 iterations (coordinate ascent).
For each expanded rectangle:
1. Test at angle - 2°
2. Test at angle + 2°
3. If either improves area, use that instead
This catches edge-aligned angular optima that skeleton PCA may miss.
Same as BCRS Stage 6:
1. Compute SDF at 4 corners + 4 edge midpoints
2. Take maximum value (SDF_max)
3. If SDF_max <= epsilon: certified
4. Else: apply symmetric shrink (SDF_max + 2*epsilon)
- If shrink > 20% of shorter side: reject
- If passes max_ratio constraint: adjust
- Re-verify
- Among all seeds, select highest-area certified rectangle
- Record diagnostics:
- rank (0 = best seed)
- s2_gain (skeleton vs edge-only)
- best_effort (1 if shrink used)
| Parameter | Default | Description |
|---|---|---|
| GRID_COARSE | 40 | Grid resolution for solve |
| GRID_FINE | 40 | Fine grid (same as coarse in Skeleton) |
| TOP_K | 5 | Maximum skeleton seed count |
| MAX_RATIO | 0 | Max aspect ratio (0 = unlimited) |
| ALWAYS_RETURN | True | Enable shrink fallback |
| ANGLE_STEP | 5.0 | Fallback sweep step |
| 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 |
| Field | Description |
|---|---|
| area | Rectangle area in CRS units |
| angle_deg | Rotation angle (0-90°) |
| ratio | Aspect ratio (long:short) |
| cand_rank | Seed rank (0 = best) |
| s2_gain | Area gain from skeleton over edge-only |
| best_effort | 1 if shrink fallback used |
| Aspect | Skeleton | BCRS |
|---|---|---|
| Seed generation | Skeleton PCA + edge angles | Edge histogram + coarse grid |
| Initial solve | Uniform grid 40×40 | Vertex-coordinate grid |
| Expansion | SDF | SDF |
| Certification | SDF | SDF |
| Fill rate (mean) | 54.96% | 55.74% |
| Time @290 | 34.64s | 26.14s |
Skeleton trades speed for different seed generation approach. Uses skeleton structure rather than edge histogram.
[1] Blum, H. (1967). A transformation for extracting new descriptors of shape. In W. Wathon (Ed.), Models for the Perception of Speech and Visual Form (pp. 362-380). MIT Press.
[2] Osher, S., & Fedkiw, R. (2003). Level Set Methods and Dynamic Implicit Surfaces. Springer.
Navigation
- Home | Installation | Algorithms | Approximation | BCRS | Axis-Aligned | Performance | Complexity | Foundations | Parameters | Folder Layout | Usage