douglas-peucker

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

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

特性

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

安装

npm install douglas-peucker

使用方法

基本用法

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 });

配置选项

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

const simplified = simplify(points, options);

在浏览器中使用

<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

// 推荐的高性能用法
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