-
Notifications
You must be signed in to change notification settings - Fork 0
Performance
Wolren edited this page Apr 30, 2026
·
5 revisions
Benchmarks run on i5-12400F, 32GB DDR4, default parameters, Numba installed, QGIS plugin (N_WORKERS=1). 290 and 5406 are the number of features in the testing dataset. Contained family removed as superseded by skeleton.
Fill rate = (rectangle area / polygon area) × 100%. Higher is better.
| Algorithm | TOP_K | Mean% | Median% | Min% | Max% | Std% | Time @290 (s) |
|---|---|---|---|---|---|---|---|
| Axis-Aligned | n/a | 35.87 | 35.43 | 3.41 | 91.69 | 17.08 | 11.81 |
| Skeleton | 3 | 54.96 | 52.58 | 8.12 | 97.52 | 21.21 | 24.64 |
| Skeleton | 1 | ~53.5 | ~51.5 | ~7.5 | ~97.5 | ~21.0 | 8.41 |
| BCRS Fast | 3 | 55.27 | 53.24 | 7.62 | 97.52 | 20.09 | 15.54 |
| BCRS Fast | 1 | ~53.5 | ~51.5 | ~7.5 | ~97.5 | ~21.0 | 7.21 |
| BCRS | 3 | 55.74 | 53.81 | 7.68 | 97.52 | 20.16 | 26.33 |
| BCRS | 1 | ~54.0 | ~52.0 | ~7.5 | ~97.5 | ~21.0 | 10.82 |
Key findings:
- Skeleton and BCRS families achieve ~55% fill rate vs ~36% for axis-aligned
- BCRS marginally leads in mean/median (+0.5-1%)
- Dropping from
top_k=3totop_k=1gives 2-3× speed with ~1.5% fill loss - BCRS Fast with
top_k=1(7.21s) rivals approximation speed (~7s) with certified contained results - Skeleton with
top_k=1(8.41s) is the fastest certified solver using BCRS-free approach - All methods reach similar max fill (~97.5%), indicating ceiling on difficult polygons
The top_k parameter acts as a slider:
| Algorithm | top_k=3 | top_k=1 | Speedup | Fill loss |
|---|---|---|---|---|
| BCRS | 26.33s | 10.82s | 2.4× | ~1.5% |
| BCRS Fast | 15.54s | 7.21s | 2.2× | ~1.5% |
| Skeleton | 24.64s | 8.41s | 2.9× | ~1.5% |
| Algorithm | TOP_K | Time @290 (s) | Time @5406 (s) | Scale |
|---|---|---|---|---|
| Approx Standard | 1 | 7.13 | 127.25 | 17.85× |
| Approx Fast | 1 | 6.98 | 125.93 | 18.04× |
| Skeleton | 3 | 24.64 | — | — |
| Skeleton | 1 | 8.41 | — | — |
| BCRS | 3 | 26.33 | — | — |
| BCRS | 1 | 10.82 | — | — |
| BCRS Fast | 3 | 15.54 | — | — |
| BCRS Fast | 1 | 7.21 | — | — |
| Axis-Aligned | n/a | 11.81 | 120.24 | 10.18× |
| Algorithm | TOP_K | Time @290 (s) |
|---|---|---|
| Approx Standard | 1 | 5.97 |
| Approx Fast | 1 | 5.90 |
| BCRS | 3 | 29.38 |
| BCRS | 1 | 12.10 |
| BCRS Fast | 3 | 19.25 |
| BCRS Fast | 1 | 8.73 |
| Skeleton | 3 | 33.02 |
| Skeleton | 1 | 10.97 |
| Axis-Aligned | n/a | 14.83 |
BCRS, BCRS Fast and Skeleton run faster serially — per‑feature overhead exceeds the parallel gain.
- Best throughput: Approx Fast (6.98s @290), then BCRS Fast top_k=1 (7.21s) — same order of magnitude with certified containment
- Best fill rate: BCRS top_k=3 (55.74% mean)
- Best speed per fill: Skeleton top_k=1 (8.41s, ~53.5% fill)
- Best scaling: Axis-Aligned (10.18× vs ~18× for grid-based solvers)
- Contained family superseded: skeleton now covers the same use-case with higher fill rate
- BCRS Fast with top_k=1 achieves speed parity with approximation while returning certified contained results — the strongest practical trade-off in the pack
See Complexity for formal analysis.
Navigation