道格拉斯算法

时间：2025-04-01 12:07:11

道格拉斯-普克抽稀算法，是用来对大量冗余的图形数据点进行压缩以提取必要的数据点。

传统的道格拉斯算法是通过递归方式实现的，如：/cdl2008sky/article/details/7701769

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

传统的道格拉斯-普克算法都是递归实现，然而有时候递归的层次太深的话会出现栈溢出的情况。在此，介绍一种非递归的算法。

改进D-P算法的具体步骤如下：

1、将首末两点加入队列，遍历队列。

2、计算出其它点到以首末点连线的直线的最大距离并和限差进行比较。

3、若大于等于限差，将这个点加入到队列中两点之间，并重新遍历序列，以相邻点作为始末点。若小于限差则将首末点中间点全部删除。

代码如下：

package ;

public class Point {

	private double x;
	private double y;
	public double getX() {
		return x;
	}
	public void setX(double x) {
		 = x;
	}
	public double getY() {
		return y;
	}
	public void setY(double y) {
		 = y;
	}
	public Point(double x, double y) {
		super();
		 = x;
		 = y;
	}
}


<pre name="code" class="java">package ;

import ;
import ;
import ;

import ;

public class Douglas {

	// 存储用于处理的点的List列表
	private List<Point> list = null;

	// 给定的阈值(限差)threshold
	private final double threshold = 1;

	public Douglas(List<Point> list) {
		 = list;
	}

	/**
	 * 道格拉斯算法，处理List<Point>序列
	 * 先将首末两点加入points序列中，然后在list序列找出距离首末点连线距离的最大距离值dmax并与阈值进行比较，
	 * 若大于阈值则将这个点加入points序列，重新遍历points序列。否则将两点间的所有点(list)移除。
	 * 
	 * @return 返回经过道格拉斯算法后得到的点的序列
	 */
	public List<Point> douglasPeucker() {
		List<Point> points = new LinkedList<>();
		// 将首末两点加入到序列中
		((0));
		((() - 1));
		for (int i = 0; i < () - 1; i++) {
			int start = ((i));
			int end = ((i + 1));
			// 比较是否是相邻点
			if (end - start == 1) {
				continue;
			}
			String value = getMaxDistance(start, end);
			double maxDist = ((",")[0]);
			// 大于限差将点加入points序列
			if (maxDist >= threshold) {
				int position = ((",")[1]);
				(i + 1, (position));
				// 将循环变量i初始化,即重新遍历points序列
				i = -1;
			} else {
				/**
				 * 将两点间的点全部删除
				 */
				int removePosition = start + 1;
				for (int j = 0; j < end - start - 1; j++) {
					(removePosition);
				}
			}
		}
		return points;
	}

	/**
	 * 根据给定的始末点，计算出距离始末点直线的最远距离和点在list列表中的位置
	 * @param start 遍历list起始点
	 * @param end 遍历list终点
	 * @return maxDiatance + "," + position 返回最大距离+","+在list中位置
	 */
	private String getMaxDistance(int start, int end) {
		double maxDiatance = -1;
		int position = -1;
		double distance = getDistance((start), (end));
		for (int i = start; i < end; i++) {
			double firstSide = getDistance((start),
					(i));
			if (firstSide < threshold) {
				continue;
			}
			double lastSide = getDistance((end), (i));
			if (lastSide < threshold) {
				continue;
			}
			// 使用海伦公式求距离
			double p = (distance + firstSide + lastSide) / 2;
			double dis = (p * (p - distance) * (p - firstSide)
					* (p - lastSide))
					/ distance;
			if (dis > maxDiatance) {
				maxDiatance = dis;
				position = i;
			}
		}
		return maxDiatance + "," + position;
	}

	// 两点间距离公式
	private double getDistance(Point first, Point last) {
		return ((() - (), 2)
				+ (() - (), 2));
	}

	public static void main(String[] args) {
		Point point0 = new Point(1, 4);
		Point point1 = new Point(2, 3);
		Point point2 = new Point(4, 2);
		Point point3 = new Point(6, 6);
		Point point4 = new Point(7, 7);
		Point point5 = new Point(8, 6);
		Point point6 = new Point(9, 5);
		Point point7 = new Point(10, 10);
		List<Point> list = new ArrayList<>();
		(point0);
		(point1);
		(point2);
		(point3);
		(point4);
		(point5);
		(point6);
		(point7);
		Douglas douglas = new Douglas(list);
		List<Point> points = ();
		for (int i = 0; i < (); i++) {
			("(" + (i).getX() + ","
					+ (i).getY() + ")");
		}
	}
}

结果为： 
 

(1.0,4.0)
(4.0,2.0)
(7.0,7.0)
(9.0,5.0)
(10.0,10.0)

 

 

相关文章