perf: Replace linear stitch proximity scan with KDTree #23

New issue

Closed

opened 2026-06-10 05:45:49 +00:00 by Mark · 0 comments

Mark commented

2026-06-10 05:45:49 +00:00

Owner

Problem

pull_compensation.py:317 — _find_nearby_stitches_of_type does a full O(n) linear scan of all stitches for every stitch. This makes apply_pull_compensation O(n²). For designs with 10,000+ stitches, this is a major bottleneck.

Proposed Fix

Pre-build a scipy.spatial.KDTree from stitch coordinates before the main loop, pre-partition stitches by type, and query neighbors in O(log n).

Impact

10-100x faster for large stitch counts.

Files

src/post_processing/pull_compensation.py:94-111, 232, 265, 299-323

## Problem `pull_compensation.py:317` — `_find_nearby_stitches_of_type` does a full O(n) linear scan of all stitches for every stitch. This makes `apply_pull_compensation` O(n²). For designs with 10,000+ stitches, this is a major bottleneck. ## Proposed Fix Pre-build a `scipy.spatial.KDTree` from stitch coordinates before the main loop, pre-partition stitches by type, and query neighbors in O(log n). ## Impact 10-100x faster for large stitch counts. ## Files - `src/post_processing/pull_compensation.py:94-111, 232, 265, 299-323`