多边形压缩 Douglas-Peucker算法

多边形压缩Douglas-Peucker算法，上代码！

#include <iostream>
#include <cmath>
#include <utility>
#include <vector>
#include <stdexcept>
#include <opencv2/opencv.hpp> // 包含OpenCV头文件

using namespace std;

typedef std::pair<double, double> Point;


//使用向量发计算高度
double PerpendicularDistance(const Point& pt, const Point& lineStart, const Point& lineEnd)
{
	double dx = lineEnd.first - lineStart.first;
	double dy = lineEnd.second - lineStart.second;

	//Normalize
	double mag = pow(pow(dx, 2.0) + pow(dy, 2.0), 0.5);
	if (mag > 0.0)
	{
		dx /= mag; dy /= mag;
	}

	double pvx = pt.first - lineStart.first;
	double pvy = pt.second - lineStart.second;

	//Get dot product (project pv onto normalized direction)
	double pvdot = dx * pvx + dy * pvy;

	//Scale line direction vector
	double dsx = pvdot * dx;
	double dsy = pvdot * dy;

	//Subtract this from pv
	double ax = pvx - dsx;
	double ay = pvy - dsy;

	return pow(pow(ax, 2.0) + pow(ay, 2.0), 0.5);
}

//递归逐一计算
void RamerDouglasPeucker(const vector<Point>& pointList, double epsilon, vector<Point>& out)
{
	if (pointList.size() < 2)
		throw invalid_argument("Not enough points to simplify");

	// Find the point with the maximum distance from line between start and end
	double dmax = 0.0;
	size_t index = 0;
	size_t end = pointList.size() - 1;
	for (size_t i = 1; i < end; i++)
	{
		double d = PerpendicularDistance(pointList[i], pointList[0], pointList[end]);
		if (d > dmax)
		{
			index = i;
			dmax = d;
		}
	}

	// If max distance is greater than epsilon, recursively simplify
	if (dmax > epsilon)
	{
		// Recursive call
		vector<Point> recResults1;
		vector<Point> recResults2;
		vector<Point> firstLine(pointList.begin(), pointList.begin() + index + 1);
		vector<Point> lastLine(pointList.begin() + index, pointList.end());
		RamerDouglasPeucker(firstLine, epsilon, recResults1);
		RamerDouglasPeucker(lastLine, epsilon, recResults2);

		// Build the result list
		out.assign(recResults1.begin(), recResults1.end() - 1);
		out.insert(out.end(), recResults2.begin(), recResults2.end());
		if (out.size() < 2)
			throw runtime_error("Problem assembling output");
	}
	else
	{
		//Just return start and end points
		out.clear();
		out.push_back(pointList[0]);
		out.push_back(pointList[end]);
	}
}

int main()
{
	vector<Point> pointList;
	vector<Point> pointListOut;

	pointList.push_back(Point(0.0, 6.0));
	pointList.push_back(Point(1.0, 1.1));
	pointList.push_back(Point(3.0, 5.0));
	pointList.push_back(Point(4.0, 6.0));
	pointList.push_back(Point(5.0, 7.0));
	pointList.push_back(Point(6.0, 8.1));
	pointList.push_back(Point(7.0, 9.0));
	pointList.push_back(Point(8.0, 9.0));
	pointList.push_back(Point(9.0, 9.0));
	pointList.push_back(Point(2.0, 10.2));

	cv::Mat canvas(200, 200, CV_8UC3, cv::Scalar(255, 255, 255)); // 创建一个300x300像素的画布

	// 显示第一个圆
	for (auto i : pointList) {
		cv::circle(canvas, cv::Point(i.first*10, i.second*10), 2, cv::Scalar(0, 0, 255), -1);
		cv::imshow("Canvas", canvas);
		cv::waitKey(300); // 等待10秒
	}
	cv::waitKey(900);

	RamerDouglasPeucker(pointList, 1.0, pointListOut);

	cout << "result" << endl;
	for (size_t i = 0; i < pointListOut.size(); i++)
	{
		cv::circle(canvas, cv::Point(pointListOut[i].first * 10, pointListOut[i].second * 10), 2, cv::Scalar(255, 0, 0), -1);
		cv::imshow("Canvas", canvas);
		cv::waitKey(300); // 等待10秒
		cout << pointListOut[i].first << "," << pointListOut[i].second << endl;
	}
	system("pause");
	return 0;
}