Sampling vs Intersection

"/home/yossef/notes/git/projects/maplibra/decisions/Sampling vs Intersection.md"

path: maplibra/decisions/Sampling vs Intersection.md

- **fileName**: Sampling vs Intersection
- **Created on**: 2026-06-16 00:48:42

Sampling vs Intersection

Purpose: Documents why point-sampling is used for wall detection instead of geometric intersection.

Decision

Wall-crossing detection uses point sampling along segments rather than true line-polygon intersection.

Context

The system needs to determine if a straight-line segment between two points crosses any wall or obstacle. This is called thousands of times during route smoothing.

Options Considered

Option A: Point Sampling (chosen)

Sample N evenly-spaced points along the segment. Check each against walkable/blocker polygons via booleanPointInPolygon.

Option B: Line-Polygon Intersection

Use turf.lineIntersect or similar to test the segment against every blocker polygon boundary.

Why Sampling Was Chosen

Performance: booleanPointInPolygon is O(vertices) per polygon. Line intersection is also O(vertices) but with more complex math per edge. With spatial indexing, sampling + point-in-polygon is fast enough.
Simplicity: The blocker polygons are pre-buffered outward. Checking if a point is inside a buffered polygon captures clearance automatically. Line intersection would need a separate clearance step.
Reuse: The same isPointWalkable function serves multiple callers (smoothing, graph build, WASM). One function, one cache.

Known Weakness

If a wall polygon (after buffering) is thinner than the sample step distance, a segment can pass completely through it without any sample landing inside.

Mitigations applied:

JS sample step reduced to 0.2m (catches walls buffered to at least 0.2m width)
WASM bridge computes distance-based samples (1 per 0.3m)
Graph builder edge step capped at 0.4m

Remaining risk: Extremely thin walls (< 0.2m after buffering) could still be missed. In practice, walls are at least 0.1m thick and get buffered by 0.6m, making the final blocker polygon > 0.7m wide — well above the sample step.

When to Revisit

If users report paths through thin partition walls, glass dividers, or barriers that are only a few cm wide in the floor plan, consider adding a line-intersection check as a secondary validation (or increasing the buffer distance for thin features).

continue:[[]]
before:[[]]