Douglas-Peucker折线的简化C++

以下是C++中实现Douglas-Peucker折线简化的代码示例：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class DouglasPeucker {
public:
    static vector<pair<double, double>> DouglasPeuckerReduction(vector<pair<double, double>>& points, double tolerance);
private:
    static double PerpendicularDistance(pair<double, double>& point, pair<double, double>& lineStart, pair<double, double>& lineEnd);
    static void DouglasPeuckerRecursive(vector<pair<double, double>>& points, int firstPoint, int lastPoint, double tolerance, vector<pair<double, double>>& simplifiedPoints);
};

vector<pair<double, double>> DouglasPeucker::DouglasPeuckerReduction(vector<pair<double, double>>& points, double tolerance) {
    vector<pair<double, double>> simplifiedPoints;
    DouglasPeuckerRecursive(points, 0, points.size() - 1, tolerance, simplifiedPoints);
    simplifiedPoints.push_back(points[points.size() - 1]);
    return simplifiedPoints;
}

double DouglasPeucker::PerpendicularDistance(pair<double, double>& point, pair<double, double>& lineStart, pair<double, double>& lineEnd) {
    double x = point.first;
    double y = point.second;
    double x1 = lineStart.first;
    double y1 = lineStart.second;
    double x2 = lineEnd.first;
    double y2 = lineEnd.second;
    double numerator = abs((y2 - y1)*x - (x2 - x1)*y + x2*y1 - y2*x1);
    double denominator = sqrt(pow(y2 - y1, 2) + pow(x2 - x1, 2));
    return numerator / denominator;
}

void DouglasPeucker::DouglasPeuckerRecursive(vector<pair<double, double>>& points, int firstPoint, int lastPoint, double tolerance, vector<pair<double, double>>& simplifiedPoints) {
    double maxDistance = 0;
    int index = 0;
    pair<double, double> lineStart = points[firstPoint];
    pair<double, double> lineEnd = points[lastPoint];
    for (int i = firstPoint + 1; i < lastPoint; i++) {
        double distance = PerpendicularDistance(points[i], lineStart, lineEnd);
        if (distance > maxDistance) {
            maxDistance = distance;
            index = i;
        }
    }
    if (maxDistance > tolerance) {
        vector<pair<double, double>> leftPoints;
        vector<pair<double, double>> rightPoints;
        DouglasPeuckerRecursive(points, firstPoint, index, tolerance, leftPoints);
        DouglasPeuckerRecursive(points, index, lastPoint, tolerance, rightPoints);
        for (int i = 0; i < leftPoints.size() - 1; i++) {
            simplifiedPoints.push_back(leftPoints[i]);
        }
        for (int i = 0; i < rightPoints.size(); i++) {
            simplifiedPoints.push_back(rightPoints[i]);
        }
    }
}

上述代码中，DouglasPeucker类实现了Douglas-Peucker算法的折线简化。其中，DouglasPeuckerReduction函数接受一个点集和一个容差值，返回一个简化后的点集。PerpendicularDistance函数计算一个点到一条直线的垂直距离。DouglasPeuckerRecursive函数是递归实现的，用于将点集分割成更小的子集并递归地简化它们。