PathSimplifier

Import it from @grafloria/engine.

PathSimplifier provides algorithms for simplifying paths

Features:

• Douglas-Peucker algorithm for optimal simplification
• Collinear point removal for straight paths
• Perpendicular distance calculations
• Configurable tolerance (epsilon)

Use cases:

• Reduce waypoint count in routed paths
• Clean up paths with unnecessary intermediate points
• Optimize path storage and rendering performance
• Maintain path shape while reducing complexity

ts
Copy
class PathSimplifier

Methods

• simplify(points: Point[], epsilon: number = this.DEFAULT_EPSILON): Point[] — Simplify a path using the Douglas-Peucker algorithm

This algorithm recursively divides the path and removes points that are within epsilon distance from the line between endpoints.

Time complexity: O(n log n) average, O(n²) worst case

• removeCollinearPoints(points: Point[], tolerance: number = 0.01): Point[] — Remove collinear points from path

This is faster than Douglas-Peucker but less sophisticated. Only removes points that lie exactly (within tolerance) on the line between their neighbors.

Time complexity: O(n)

• arePointsCollinear( p1: Point, p2: Point, p3: Point, tolerance: number = 0.01 ): boolean — Check if three points are collinear (lie on the same line)

Uses cross product to determine collinearity. If cross product is close to zero, points are collinear.

• perpendicularDistance( point: Point, lineStart: Point, lineEnd: Point ): number — Calculate perpendicular distance from point to line segment

Uses the formula: distance = |((y2-y1)x0 - (x2-x1)y0 + x2y1 - y2x1)| / sqrt((y2-y1)² + (x2-x1)²)

• calculatePathLength(points: Point[]): number — Calculate total path length

Useful for comparing simplified vs original paths

• getSimplificationStats(original: Point[], simplified: Point[]) — Get simplification statistics

Example

typescript
Copy
const simplifier = new PathSimplifier();

// Remove collinear points (fastest)
const cleaned = simplifier.removeCollinearPoints(points);

// Douglas-Peucker simplification (optimal)
const simplified = simplifier.simplify(points, epsilon);