-
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. 290 and 5406 are the number of features in the testing dataset.
Fill rate = (rectangle area / polygon area) × 100%. Higher is better.
| Algorithm | Mean% | Median% | Min% | Max% | Std% | Time @290 (s) |
|---|---|---|---|---|---|---|
| Axis-Aligned | 35.87 | 35.43 | 3.41 | 91.69 | 17.08 | 12.98 |
| Skeleton | 54.96 | 52.58 | 8.12 | 97.52 | 21.21 | 34.64 |
| BCRS Fast | 55.27 | 53.24 | 7.62 | 97.52 | 20.09 | 15.28 |
| BCRS | 55.74 | 53.81 | 7.68 | 97.52 | 20.16 | 26.14 |
Key findings:
- Skeleton and BCRS families achieve ~55% fill rate vs ~36% for axis-aligned
- BCRS marginally leads in mean/median fill rate (+0.5-1%)
- Skeleton runs 2.3× slower than BCRS Fast but uses different seed generation
- All methods reach similar max fill (~97.5%), indicating ceiling on difficult polygons
| Algorithm | TOP_K | Time @290 (s) | Time @5406 (s) | Best Mode |
|---|---|---|---|---|
| Approx Fast | 1 | 6.98 | 125.93 | 12w+chunk |
| Axis-Aligned | n/a | 11.81 | 120.24 | 1w |
| Skeleton | 5 | 34.64 | TBD | 12w |
| BCRS Fast | 3 | 23.61 | 445.01 | 1w |
| BCRS | 3 | 26.14 | TBD | 1w |
| Profile | Algorithm | TOP_K | Time @290 (s) | Time @5406 (s) | Scale |
|---|---|---|---|---|---|
| P1 | Approx Standard | 1 | 7.13 | 127.25 | 17.85x |
| P2 | Approx Fast | 1 | 6.98 | 125.93 | 18.04x |
| P3 | Skeleton | 5 | 34.64 | TBD | TBD |
| P4 | BCRS Fast | 3 | 23.61 | 445.01 | 18.85x |
| P5 | Axis-Aligned | n/a | 11.81 | 120.24 | 10.18x |
- Best throughput: Approx Fast (6.98s @290)
- Best fill rate: BCRS (55.74% mean) - marginally ahead of Skeleton
- Best scaling: Axis-Aligned (10.18x vs ~18x for others)
- BCRS/Axis-Aligned: Negative speedup with multithreading
See Complexity for formal analysis.
Navigation