[数据结构与算法]道格拉斯普克算法（简化线段点）

1、算法原理

道格拉斯普克算法（Douglas-Peukcer）算法是一种简化线状要素的经典算法。先介绍其原始的计算原理：

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

算法的详细步骤如下:

(1) 在曲线首尾两点间虚连一条直线,求出其余各点到该直线的距离，如图（1）。

(2) 选其最大者与阈值相比较,若大于阈值,则离该直线距离最大的点保留,否则将直线两端点间各点全部舍去，如图（2），第4点保留。

(3) 依据所保留的点,将已知曲线分成两部分处理,重复第1、2步操作，迭代操作，即仍选距离最大者与阈值比较,依次取舍,直到无点可舍去，最后得到满足给定精度限差的曲线点坐标，如图（3）、（4）依次保留第6点、第7点，舍去其他点,即完成线的化简。

2、程序编程思想

可以发现DP算法是一个不断递归的过程，直至不再划分成两部分为止，其类似构建二叉树的过程。首先对输入的一组点，判断其是否需要分裂。

当最大距离大于阈值时，需要进行划分成左右两部分（以4号点断开），如下图所示：

?

对于每一部分，采用上边类似的思想，判断递归下去，直至不再分成左右两棵树。

?

3、代码示例：

?

void BuildTree(DPNode *&root, vector<pcl::PointXYZ> points, pcl::PointXYZ headpoint, pcl::PointXYZ endpoint, double thres_ds)
{
	arrayoperation ArrExample;
	//创建一个新的根节点
	root = new DPNode;
	root->points = points;
	root->HeadPoint = headpoint;
	root->EndPoint = endpoint;

	if (points.size() <= 2)//点数少于2个的，不再进行划分
	{
		
		root->Left_node = NULL;
		root->Right_node = NULL;
		root->NodeType = false;//不能再划分
	}
	else
	{
		vector<double> disvec;//计算每个点到首尾两点构成直线的距离
		for (int i = 0; i < points.size(); i++)
		{
			double tempds = Point2Dline(points[i], headpoint, endpoint);
			disvec.push_back(tempds);
		}
		double maxds = ArrExample.getMax_vector(disvec);
		double maxindex = ArrExample.GetIndexOfMax(disvec);//若整个点数为10个，那么maxindex一定是介于 2到9之间，因为不可能取首尾两个点，首尾点到直线的距离为0

		if (maxds < thres_ds)//小于阈值的，不再分割
		{
			root->Left_node = NULL;
			root->Right_node = NULL;
			root->NodeType = false;//不能再划分
		}
		else
		{
			root->NodeType = true;//可以继续划分

			//将点划分成2部分，左边与右边
			vector<pcl::PointXYZ> Leftpointsvec, Rightpointsvec;
			for (int i = 0; i < points.size(); i++)
			{
				if (i <= maxindex)
				{
					Leftpointsvec.push_back(points[i]);//左边树包含的点
				}
			}

			for (int i = 0; i < points.size(); i++)
			{
				if (i >= maxindex)
				{
					Rightpointsvec.push_back(points[i]);//右边树包含的点
				}
			}
			//左边子树的头部点与尾部点
			pcl::PointXYZ left_headpoint = headpoint;
			pcl::PointXYZ left_endpoint = points[maxindex];

			//右边子树的头部点与尾部点
			pcl::PointXYZ right_headpoint = points[maxindex];
			pcl::PointXYZ right_endpoint = endpoint;

			//创建左、右树
			root->Right_node = new DPNode();
			BuildTree(root->Left_node, Leftpointsvec, left_headpoint, left_endpoint, thres_ds);
			BuildTree(root->Right_node, Rightpointsvec, right_headpoint, right_endpoint, thres_ds);
		}
	}
}