道格拉斯-普克算法，根据wiki，全名“Ramer–Douglas–Peucker algorithm”   是一种采用迭代式方法对折线进行压缩的方法，选取一些特征点代表原折线，并且保证原折线的点距离压缩后的折线不超过一定的范围阈值\(d\)。

即已知折线\(l_{old}= (X_1,X_2,…,X_n)\),求索引序列\(\{1,?,…,?,n\}\),使得原点集到压缩后的新折线\(l_{new}=(X_1,X_?,…,X_?,X_n)\)的距离小于\(d\)。算法思路是：

1）初始连接\(X_1X_n\),计算\(X_2,…,X_{n-1}\)到\(X_1X_n\)的距离，并将最大距离值\(d_i\)与\(d\)比较，并且记录最大距离对应的节点\(X_i\)。如果\(d_i<d\);算法终止。

2）如果\(d_i>=d\),则将\(X_1X_n\)分为\(X_1X_i\)与\(X_iX_n\)两部分，对于每一部分，分别执行步骤1,注意此时步骤一对应的起终点应该分别为\( [1,i] ,[i,n] \)。

3）所有分支全部终止之后，记录到的\(\{(X_i)\} \)序列就是所求的节点序列。

插一副wiki上面的图片，直观的记录了算法处理流程。

我实现的C++版本的道格拉斯-普克算法如下

//点，向量共用结构
struct point
{
	double x;
	double y;
	double z;
	
	//向量点乘
	double operator* (const point&);
	point operator-(const point&);
	point operator*(double);
	point(double,double,double);
	//正则化，将vector 变为单位向量。
	void nomorlize();
	//向量长度
	double length();
};

typedef point vector3d;

double point_to_line_distance(const point& p,const point& p0,const point& p1)
{
	//向量 p1-p0
	vector3d v(p1.x-p0.x,p1.y-p0.y,p1.z-p0.z);
	//向量 p	-p0
	vector3d v1(p.x-p0.x ,p.y-p0.y ,p.z - p0.z);
	v.nomorlize();

	return (v1 - v*(v1*v)).length();
}

void _douglas_peucker_compress(const std::vector<point>& vecPoints,double d, int start,int end ,std::vector<int>& indexs)
{
	//参入参数判断
	if(start>=end)
		return ;

	//首末点
	const point& start_point = vecPoints[start];
	const point& end_point = vecPoints[end];
	
	double d_max = -1; //记录 (start,end)中点到直线的最大距离
	int max_index =-1; //距离 最大距离对应的点序号

	for(int i=start+1;i<end;i++)
	{
		double distance = point_to_line_distance(vecPoints[i],start_point,end_point);
		if(distance>d_max)
		{
			d_max = distance;
			max_index =i;
		}
	}
	
	if(d_max>d)
	{
		//注意，因为节点的顺序问题，这两个函数的调用顺序不能写反！
		//在做并行化的时候也需要注意
		_douglas_peucker_compress(vecPoints,d,start,max_index,indexs);
		_douglas_peucker_compress(vecPoints,d,max_index,end,indexs);
	}else
	{
		//将end加入indexs;
		indexs.push_back(end);
	}

}

void douglas_peucker_compress(const std::vector<point>& vecPoints,double d,std::vector<int>& indexs)
{
	indexs.clear();
	indexs.push_back(0); //加入首点
	//调用递归算法深度优先方式加入索引点
	_douglas_peucker_compress(vecPoints,d,0,vecPoints.size()-1,indexs);
}

其中，向量的 重载运算符，模长，单位向量化算法略去实现。