# douglas-peucker

A high-performance implementation of the Douglas-Peucker line simplification algorithm, supporting multiple data formats for input and output.

The Douglas-Peucker algorithm is a commonly used trajectory point simplification algorithm that effectively reduces redundant points in point sequences, significantly reducing data volume while preserving the original shape characteristics.

## Features

- 🚀 **High Performance**: Non-recursive optimized implementation to avoid stack overflow risks
- 📦 **Multi-format Support**: Supports both flat arrays `[x, y, x, y, ...]` and coordinate pair arrays `[[x, y], [x, y], ...]`
- ⚙️ **Flexible Configuration**: Supports custom tolerance values and high-precision calculation mode
- 🌐 **TypeScript Support**: Complete TypeScript type definitions
- 📦 **Modern Build**: Supports both CommonJS and ES Module formats

## Installation

```bash
npm install douglas-peucker
```

## Usage

### Basic Usage

```typescript
import { simplify } from 'douglas-peucker';

// Using flat array format (recommended for best performance)
const points = new Float32Array(10000);
for (let i = 0; i < points.length; i++) {
    points[i] = Math.random() * 1000;
}
const simplified = simplify(points, { tolerance: 1.0 });

// Using regular array format
const pointsArray = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4];
const simplifiedArray = simplify(pointsArray, { tolerance: 1.0 });

// Using coordinate pair array format
const pointPairs = [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]];
const simplifiedPairs = simplify(pointPairs, { tolerance: 1.0 });
```

### Configuration Options

```typescript
const options = {
  tolerance: 1.0,      // Tolerance value, default is 1.0
  highQuality: false   // Whether to enable high-precision calculation, default is false
};

const simplified = simplify(points, options);
```

### Usage in Browser

```html
<script type="module">
  import { simplify } from 'douglas-peucker/dist/index.mjs';
  
  const points = new Float32Array(10000);
  for (let i = 0; i < points.length; i++) {
    points[i] = Math.random() * 1000;
  }
  const simplified = simplify(points, { tolerance: 1.0 });
</script>
```

## API

### `simplify(coords, options?)`

Simplifies coordinate sequences using the Douglas-Peucker algorithm

#### Parameters

- `coords`: Coordinate array, supporting three formats:
  - Float32Array: `new Float32Array([x, y, x, y, ...])` (best performance)
  - Regular array: `[x, y, x, y, ...]`
  - Coordinate pair array: `[[x, y], [x, y], ...]`
- `options` (optional): Configuration object
  - `tolerance`: Simplification tolerance value, default is `1.0`
  - `highQuality`: Whether to preserve highest precision, default is `false`

#### Return Value

Simplified coordinate array, format consistent with input.

## Performance Optimization Recommendations

For optimal performance, it is recommended to:

1. Use `Float32Array` type to store coordinate data
2. Pre-allocate array size to avoid dynamic resizing
3. Consider using Web Workers for large data processing

```typescript
// Recommended high-performance usage
const coords = new Float32Array(10000);
for (let i = 0; i < coords.length; i++) {
    coords[i] = Math.random() * 1000;
}
const simplified = simplify(coords, { tolerance: 1.0 });
```

## Algorithm Principle

The Douglas-Peucker algorithm is a recursive algorithm with the basic idea:

1. Connect the first and last points to form a line segment
2. Calculate the distance from all points to this line segment
3. Find the point with the maximum distance
4. If the maximum distance is greater than the given threshold, keep that point and recursively execute the algorithm on both sides
5. Otherwise, only keep the first and last points

This implementation uses a non-recursive optimized version, using an explicit stack instead of recursive calls to improve performance and avoid stack overflow issues.

## Performance Characteristics

- Bit operations to optimize index calculations
- Pre-allocated memory to avoid frequent GC
- Early termination condition checks
- Efficient distance calculation algorithms
- Float32Array data type optimizes memory usage and access speed

## License

MIT