道格拉斯普克算法在画导线中的应用

· 在曲线首尾两点A，B之间连接一条直线AB，该直线为曲线的弦；

· 得到曲线上离该直线段距离最大的点C，计算其与AB的距离d；

· 比较该距离与预先给定的阈值threshold的大小，如果小于threshold，则该直线段作为曲线的近似，该段曲线处理完毕。

· 如果距离大于阈值，则用C将曲线分为两段AC和BC，并分别对两段取弦进行1~3的处理。

· 当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即可以作为曲线的近似。

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 {
    // flags[ind0] = true;
    // flags[ind1] = true;
    if (ind1 - ind0 <= 1) {
      return;
    }
    // 在曲线首尾两点A，B之间连接一条直线AB，该直线为曲线的弦；
    const p0: IPoint = vertexs[ind0];
    const p1: IPoint = vertexs[ind1];
    // 得到曲线上离该直线段距离最大的点C，计算其与AB的距离d；
    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;
      }
    }
    // 比较该距离与预先给定的阈值threshold的大小，如果小于threshold，则该直线段作为曲线的近似，该段曲线处理完毕。
    if (maxD < threshold) {
      return;
    }
    // 如果距离大于阈值，则用C将曲线分为两段AC和BC，并分别对两段取弦进行1~3的处理。
    flags[maxInd] = true;
    SimplifyPathUtil.simplifySeg(vertexs, threshold, ind0, maxInd, flags);
    SimplifyPathUtil.simplifySeg(vertexs, threshold, maxInd, ind1, flags);
  }
}

/**
 * 点到线段的最短距离
 * @param p
 * @param p1
 * @param p2
 * @returns {number}
 */
public static distancePointToSegment(p: IPoint, p1: IPoint, p2: IPoint): number {
  const pt: IPoint = LineUtil.pointToSegmentDisPoint(p, p1, p2);
  return PointUtils.distance(pt, p);
}

/**
 * 点到线段的最短距离的点。
 * @param p
 * @param p1
 * @param p2
 * @returns {IPoint}
 */
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
  };
}

/**
 * 两点之间的距离
 * @param p1
 * @param p2
 * @returns {number}
 */
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);
}

/**
 * 抽象的点。
 */
export interface IPoint {
  x: number;
  y: number;
}

为什么要抽离出来

为什么要用算法

建模思想

· 发现问题、提出问题

· 分析问题、建立模型

· 找到算法、求解模型

· 代入回去、解决问题