# 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
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 + x2*y1 - y2*x1)| / 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
const simplifier = new PathSimplifier();

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

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