多边形压缩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;
}