Simplifying Mouse-Drawn Paths Using the Douglas-Peucker Algorithm (TypeScript Implementation)

In electrical experiment simulations, wires can be created either from a component library or by drawing with the mouse, but densely sampled points cause poor rendering and editing issues.

The Douglas‑Peucker algorithm (also known as Ramer‑Douglas‑Peucker) reduces the number of points while preserving the shape, offering translation and rotation invariance and deterministic results given a threshold.

The algorithm recursively connects the first and last points of a segment, finds the point with maximum perpendicular distance, and keeps it if the distance exceeds a threshold, otherwise discarding intermediate points.

Implementation in TypeScript is provided via the SimplifyPathUtil class, which includes a simplify method and a private simplifySeg recursive helper. Supporting utilities LineUtil.distancePointToSegment, LineUtil.pointToSegmentDisPoint, and PointUtil.distance compute geometric distances, and the IPoint interface defines point objects.

export class SimplifyPathUtil {
  /**
   * 使用 Douglas-Peucker 算法对曲线进行化简
   * @param vertexs 构成曲线的点
   * @param threshold 阈值 点到相邻两点所构成的线段的距离小于阈值时，可以被去掉。
   * @return {IPoint[]} 平滑后的点的数组
   */
  public static simplify(vertexs: IPoint[], threshold: number): IPoint[] {
    const flags: boolean[] = [];
    flags[0] = true;
    flags[vertexs.length - 1] = true;
    SimplifyPathUtil.simplifySeg(vertexs, threshold * threshold, 0, vertexs.length - 1, flags);
    const result: IPoint[] = [];
    for (let i: number = 0; i < vertexs.length; i++) {
      if (flags[i]) {
        result.push(vertexs[i]);
      }
    }
    return result;
  }

  private static simplifySeg(vertexs: IPoint[], threshold: number, ind0: number, ind1: number, flags: boolean[]): void {
    if (ind1 - ind0 <= 1) {
      return;
    }
    const p0: IPoint = vertexs[ind0];
    const p1: IPoint = vertexs[ind1];
    let maxD: number = 0;
    let maxInd: number = -1;
    for (let i: number = ind0 + 1; i < ind1; i++) {
      const p: IPoint = vertexs[i];
      const d: number = LineUtil.distancePointToSegment(p, p0, p1);
      if (d > maxD) {
        maxD = d;
        maxInd = i;
      }
    }
    if (maxD < threshold) {
      return;
    }
    flags[maxInd] = true;
    SimplifyPathUtil.simplifySeg(vertexs, threshold, ind0, maxInd, flags);
    SimplifyPathUtil.simplifySeg(vertexs, threshold, maxInd, ind1, flags);
  }
}

public static distancePointToSegment(p: IPoint, p1: IPoint, p2: IPoint): number {
  const pt: IPoint = LineUtil.pointToSegmentDisPoint(p, p1, p2);
  return PointUtils.distance(pt, p);
}

public static pointToSegmentDisPoint(p: IPoint, p1: IPoint, p2: IPoint): IPoint {
  const cross: number = (p2.x - p1.x) * (p.x - p1.x) + (p2.y - p1.y) * (p.y - p1.y);
  if (cross <= 0) {
    return p1;
  }
  const d2: number = (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
  if (cross >= d2) {
    return p2;
  }
  const r: number = cross / d2;
  return {
    x: p1.x + (p2.x - p1.x) * r,
    y: p1.y + (p2.y - p1.y) * r
  };
}

public static distance(p1: IPoint, p2: IPoint): number {
  const dx: number = p1.x - p2.x;
  const dy: number = p1.y - p2.y;
  return Math.sqrt(dx * dx + dy * dy);
}

The result is a simplified polyline that improves rendering performance and stability, demonstrating the benefits of extracting the algorithm into a reusable module.