hanyeah

用鼠标画线，得到的点会很多，怎么样可以进行优化，去掉一些点，就像flash中的铅笔工具那样。

通过搜素，发现了道格拉斯普克(Douglas-Peuker)算法。

道格拉斯-普克算法(Douglas–Peucker algorithm，亦称为拉默-道格拉斯-普克算法、迭代适应点算法、分裂与合并算法)是将曲线近似表示为一系列点，并减少点的数量的一种算法。它的优点是具有平移和旋转不变性，给定曲线与阈值后，抽样结果一定。

道格拉斯-普克算法(Douglas–Peucker algorithm，亦称为拉默-道格拉斯-普克算法、迭代适应点算法、分裂与合并算法)是将曲线近似表示为一系列点，并减少点的数量的一种算法。该算法的原始类型分别由乌尔斯·拉默（Urs Ramer）于1972年以及大卫·道格拉斯（David Douglas）和托马斯·普克（Thomas Peucker）于1973年提出，并在之后的数十年中由其他学者予以完善。

算法的基本思路是:对每一条曲线的首末点虚连一条直线,求所有点与直线的距离,并找出最大距离值dmax ,用dmax与限差D相比:若dmax<D,这条曲线上的中间点全部舍去;若dmax ≥D,保留dmax 对应的坐标点,并以该点为界,把曲线分为两部分,对这两部分重复使用该方法。

经典的Douglas-Peucker算法步骤如下： 

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

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

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

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

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

代码如下(typescript)

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

用到了LineUtil中的方法，计算点到线段的距离，代码如下：

    /**
     * 点到线段的最短距离
     * @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
      };
    }

PointUtil中计算两点的距离，代码如下

    /**
     * 两点之间的距离
     * @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);
    }

IPoint的定义

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

参考资料：

计算几何-道格拉斯普克(Douglas-Peuker)算法

 * adobe的工具

 * https://helpx.adobe.com/illustrator/using/simplify_paths.html

 * https://help.adobe.com/en_US/as3/mobile/WS948100b6829bd5a6441c2d912897db4bb0-8000.html

 * 

 * 参考：

 * https://pro.arcgis.com/zh-cn/pro-app/tool-reference/cartography/simplify-polygon.htm

 * https://github.com/mattdesl/simplify-path  一个开源库，实现了Douglas-Peuker算法

 * https://stackoverflow.com/questions/3032630/optimizing-simplifying-a-path

 * 

 * Douglas-Peucker算法：

 * https://zhuanlan.zhihu.com/p/136286488

 * https://blog.csdn.net/qq_34510308/article/details/64539434

 * https://www.cnblogs.com/atong/archive/2013/03/06/2946539.html

 * http://paperjs.org/tutorials/paths/smoothing-simplifying-flattening/   很强大，不光有Douglas-Peuker算法，还有平滑算法。可以拿来用或者拿来学习。

《空间轨迹分析与应用》