Performance

Performance Benchmarks

Benchmarks run on i5-12400F, 32GB DDR4, default parameters, Numba installed. 290 and 5406 are the number of features in the testing dataset.

Baseline Profile (N_WORKERS=1, USE_CHUNKING=False)

Profile	Algorithm	ALWAYS_RETURN	Time @290 (s)	Time @5406 (s)	Scale Ratio
P1	Approximation Standard	n/a	7.13	127.25	17.85
P2	Approximation Fast	n/a	6.98	125.93	18.04
P3	Contained Standard	False (strict)	30.45	574.13	18.85
P4	Contained Standard	True (fallback)	30.75	573.59	18.65
P5	Contained Fast	True (fallback)	12.25	226.05	18.45
P6	BCRS	False (strict)	42.91	772.05	17.99
P7	BCRS	True (fallback)	42.35	788.03	18.61
P8	BCRS Fast	True (fallback)	23.61	445.01	18.85
P9	Axis-Aligned LIR	True (fallback)	11.81	120.24	10.18

Parallel Profile (N_WORKERS=12, USE_CHUNKING=False)

Profile	Algorithm	Time @290 (s)	Time @5406 (s)	Scale Ratio
P1	Approximation Standard	5.97	112.30	18.81
P2	Approximation Fast	5.90	108.43	18.38
P3	Contained Standard	22.27	405.91	18.23
P4	Contained Standard	22.05	410.21	18.60
P5	Contained Fast	12.03	224.82	18.69
P6	BCRS	51.83	925.01	17.85
P7	BCRS	50.88	941.69	18.51
P8	BCRS Fast	29.84	557.11	18.67
P9	Axis-Aligned LIR	14.83	158.53	10.69

Parallel + Chunking Profile (N_WORKERS=12, USE_CHUNKING=True)

Profile	Algorithm	Time @290 (s)	Time @5406 (s)	Scale Ratio
P1	Approximation Standard	6.04	109.76	18.17
P2	Approximation Fast	5.90	108.43	18.38
P3	Contained Standard	21.98	405.95	18.47
P4	Contained Standard	21.96	405.15	18.45
P5	Contained Fast	12.01	224.82	18.72
P9	Axis-Aligned LIR	14.91	157.89	10.59

Quick Comparison (Best Mode)

Algorithm	Time @290 (s)	Time @5406 (s)	Best Mode
Approximation Fast	6.98	125.93	12w+chunk
Axis-Aligned LIR	11.81	120.24	1w
Contained Fast	12.25	226.05	12w+chunk
BCRS Fast	23.61	445.01	1w

Key Observations

1. Fastest overall: Approximation Fast (6.98s @290)
2. Best for large datasets: Axis-Aligned LIR scales better (10.18x vs ~18x for others)
3. Best accuracy/performance: BCRS Fast for rotated rectangles
4. Worst scaling: Axis-Aligned LIR (best for large polygons - fewer vertices per feature)

Scaling Exponents

Algorithm	1 Worker	12 Workers
Approximation Standard	0.9851	1.0031
Approximation Fast	0.9888	0.9951
Contained Standard (strict)	1.0039	0.9923
BCRS (strict)	0.9879	0.9851
Axis-Aligned LIR	1.0058	1.0067

All exponents ≈ 1.0 indicate linear scaling.

Parallel Efficiency

Algorithm	Speedup @290	Efficiency @290
Approx Standard	1.19	9.95%
Approx Fast	1.18	9.86%
Contained Standard	1.37	11.39%
Contained Fast	1.02	8.49%
BCRS	0.83	6.90%
BCRS Fast	0.79	6.59%
Axis-Aligned LIR	0.80	6.63%

Note: BCRS and Axis-Aligned show negative speedup (slower with multithreading) due to per-feature computation time being too short to offset synchronization overhead.

Recommendations

Use Case	Recommended Algorithm
Quick candidates, large datasets	Approximation Fast (12w)
Exact axis-aligned solution	Axis-Aligned LIR (1w)
Guaranteed containment	Contained Fast (12w)
Maximum accuracy (rotated)	BCRS Fast (1w)

---

Navigation

• Home | Installation | Algorithms | Approximation | Contained | BCRS | Axis-Aligned | Complexity | Foundations | Parameters | Folder Layout | Usage