# douglas-peucker

一个高性能的 Douglas-Peucker 线状要素抽稀算法实现库，支持多种数据格式输入输出。

Douglas-Peucker 算法是一种常用的轨迹点抽稀算法，能够有效减少点序列中的冗余点，在保持原始形状特征的同时显著降低数据量。

## 特性

- 🚀 **高性能**: 采用非递归优化实现，避免栈溢出风险
- 📦 **多格式支持**: 支持平铺数组 `[x, y, x, y, ...]` 和坐标对数组 `[[x, y], [x, y], ...]` 两种格式
- ⚙️ **灵活配置**: 支持自定义容差值和高精度计算模式
- 🌐 **TypeScript 支持**: 完整的 TypeScript 类型定义
- 📦 **现代化构建**: 支持 CommonJS 和 ES Module 两种模块格式

## 安装

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

## 使用方法

### 基本用法

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

// 使用平铺数组格式（推荐，性能最佳）
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 });

// 使用普通数组格式
const pointsArray = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4];
const simplifiedArray = simplify(pointsArray, { tolerance: 1.0 });

// 使用坐标对数组格式
const pointPairs = [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]];
const simplifiedPairs = simplify(pointPairs, { tolerance: 1.0 });
```

### 配置选项

```typescript
const options = {
  tolerance: 1.0,      // 容差值，默认为 1.0
  highQuality: false   // 是否启用高精度计算，默认为 false
};

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

### 在浏览器中使用

```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?)`

对坐标序列进行 Douglas-Peucker 算法简化

#### 参数

- `coords`: 坐标数组，支持以下三种格式:
  - Float32Array: `new Float32Array([x, y, x, y, ...])` (性能最佳)
  - 普通数组: `[x, y, x, y, ...]`
  - 坐标对数组: `[[x, y], [x, y], ...]`
- `options` (可选): 配置对象
  - `tolerance`: 简化容差值，默认为 `1.0`
  - `highQuality`: 是否保留最高精度，默认为 `false`

#### 返回值

简化后的坐标数组，格式与输入保持一致。

## 性能优化建议

为了获得最佳性能，建议：

1. 使用 `Float32Array` 类型存储坐标数据
2. 预分配数组大小避免动态扩容
3. 对于大量数据处理，考虑使用 Web Workers

```typescript
// 推荐的高性能用法
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 });
```

## 算法原理

Douglas-Peucker 算法是一种递归算法，其基本思想是：

1. 连接首尾两点形成一条直线段
2. 计算所有点到该直线段的距离
3. 找到距离最大的点
4. 如果最大距离大于给定阈值，则保留该点，并对两侧分别递归执行算法
5. 否则，只保留首尾两点

本实现采用非递归优化版本，使用显式栈替代递归调用，提高了性能并避免了栈溢出问题。

## 性能特点

- 使用位运算优化索引计算
- 预分配内存避免频繁 GC
- 提前终止条件判断
- 高效的距离计算算法
- Float32Array 数据类型优化内存使用和访问速度

## 许可证

MIT