前言

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

因为网上关于道格拉斯普克算法的讲解很多，主要是使用递归实现的，这里就不赘述了。

远程仓库地址：

---

 

直接上代码和演示

//概化折线 道格拉斯普克算法	/**	 * 根据中间点到首尾点的连线的距离与阈值的关系判断是否保留某点	 * @param threshold 阈值越小，保留的点越多，抽稀程度低；阈值越大，删除的点越多，抽稀程度高	 * @return	 */	public Polyline simplify_Douglas_Peucker(double threshold) {		//初始化		for(Point point:this.getPoints()) {			point.setEnable(true);		}		List
    
      selectedPoints = new ArrayList<>();		Collections.addAll(selectedPoints,  new  Point[this.points.size()]); 		Collections.copy(selectedPoints, this.points);		simplify(selectedPoints, threshold);		//标记了删除的点，全部删掉		Iterator
     
       iterator = selectedPoints.iterator();		while (iterator.hasNext()) {			Point point = (Point) iterator.next();			if(!point.isEnable()) {				iterator.remove();			}		}		if(debug) {			System.out.println("最后保留的点：");			for(Point p:selectedPoints) {				System.out.println(p.toString());			}		}		//恢复		for(Point point:this.getPoints()) {			point.setEnable(true);		}				return new Polyline(selectedPoints);	}
     
    

/**	 * 	 * @param polyline 折线	 * @param threshold 阈值越小，保留的点越多，抽稀程度低；阈值越大，删除的点越多，抽稀程度高	 * @return	 */	public static Polyline simplify_Douglas_Peucker(Polyline polyline,double threshold) {		return polyline.simplify_Douglas_Peucker(threshold);	}		//抽稀点	private static void simplify(List
    
      points,double threshold) {		//threshold = Math.abs(threshold);		if(points.size()<3) {			return;		}		Line line = new Line(points.get(0),points.get(points.size()-1));		Point maxPoint = null;		double maxDis = 0;		//System.out.println(points.size());		for(Point point:points) {			double dis =  line.getDistancefromPoint(point);			if(debug) {				System.out.println(point.toString());			}			//System.out.println(dis);			if(Double.doubleToLongBits(dis)>Double.doubleToLongBits(maxDis) && line.getStart()!=point && line.getEnd()!=point) {				maxDis = dis;				maxPoint = point;			}					}		if(debug) {			System.out.println("max:"+maxDis);			System.out.println("阈值:"+threshold);			System.out.println("保留最大点与首尾点");		}		//保留最大点与首尾点		if(maxDis>threshold && maxPoint!=null) {			if(debug) {				System.out.println("最大点:"+maxPoint.toString());			}						//涉及到删除元素不可以用for或while循环，因为会改变元素的位置			Iterator
     
       iterator = points.iterator();			while (iterator.hasNext()) {				Point p = (Point) iterator.next();				if(!(p==line.getStart()||p==line.getEnd()||p==maxPoint)) {					//标记不可用，这里指删除					//因为还需要留着左右部分的点做进一步的简化，不可以在这里进行删除操作 防止被gc掉					p.setEnable(false);					if(debug) {						System.out.println("删除的点："+p.toString());					}				}else {					p.setEnable(true);					if(debug) {						System.out.println("保留的点："+p.toString());					}				}			}			//以maxPoint把折线分为两部分接着简化			List
      
        leftPart = points.subList(0, points.indexOf(maxPoint)+1);			List
       
         rightPart = points.subList(points.indexOf(maxPoint), points.size());			if(debug) {				System.out.println(String.format("left [1]-[%d]", points.indexOf(maxPoint)+1));				System.out.println(String.format("right [%d]-[%d]", points.indexOf(maxPoint)+1, points.size()));			}			simplify(leftPart, threshold);			simplify(rightPart, threshold);		//只保留首尾点		}else {			Iterator
        
          iterator = points.iterator();			while (iterator.hasNext()) {				Point p = (Point) iterator.next();				if(!(p.equals(line.getStart())||p.equals(line.getEnd()))) {					p.setEnable(false);					if(debug) {						System.out.println("删除的非首尾点："+p.toString());					}				}else {					if(debug) {						System.out.println("保留的首尾点："+p.toString());					}					p.setEnable(true);				}			}		}	}
        
       
      
     
    

结果：

原始图像：

 

道格拉斯普克算法概化 阈值 130：

 

道格拉斯普克算法概化 阈值 180：

 

 

道格拉斯普克算法概化 阈值  250：

 

控制台打印：