// 计算一点到一条直线（已知两点）的距离

double disP2L(CMyPoint* first, CMyPoint* last, CMyPoint* third) //first和last分别为线的两端，third是第三点

																//CMyPoint是点的类型，可以换成CPoint

{

	double x0 = first->Getx();

	double y0 = first->Gety();

	double x1 = last->Getx();

	double y1 = last->Gety();

	double x = third->Getx();

	double y = third->Gety();

	//diSquare是d²，不开方，耗时更短。

	double disSuqare = ((y0 - y1)*x + (x1 - x0)*y + (x0*y1 - x1*y0))*((y0 - y1)*x + (x1 - x0)*y + (x0*y1 - x1*y0)) / ((x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0));

	return disSuqare;

}

// Douglas–Peucker法，20190220，压缩，zf

void DP(vector<CMyPoint*> inputLine)        //输入是包含指针的数组，vector类型

{

	if (inputLine.size() <= 2)              //若少于两点，直接返回

		return;

	int size = inputLine.size();

	CMyPoint *first = inputLine[0];         //定义首点

	CMyPoint *last = inputLine[size - 1];   //定义尾点

	while (last->Getx() == first->Getx() && last->Gety() == first->Gety()) {//若首尾相同，则换点

		size = size - 1;

		last = inputLine[size - 1];

	}

	int flag = 0;                            //标记距离最大的点的下标

	double disSquare = 0;

	for (int i = 1; i<inputLine.size() - 1; i++) {

		double temp = disP2L(first, last, inputLine[i]);

		if (temp>disSquare) {                //记录最大距离及编号

			disSquare = temp;

			flag = i;

		}

	}

	if (disSquare<4) {                       //判断值与阈值的关系,阈值自己设定

		out_DP.push_back(first);             //如果小于阈值，则保留首尾点

		out_DP.push_back(last);              //out_DP是一个全局变量，vector<CMyPoint*> out_DP

		                                     //用于存储留下来的点,是最后的成果

	}

	else {                                   //否则分成两段

		vector<CMyPoint*> head, rear;

		for (int j = 0; j<inputLine.size(); j++) {

			if (j <= flag) head.push_back(inputLine[j]);

			if (j >= flag) rear.push_back(inputLine[j]);

		}

		DP(head);                            //迭代进行

		DP(rear);

	}

}