轨迹压缩之Douglas-Peucker算法之C++实现

好的，我会回答你的问题。首先，Douglas-Peucker算法是一种轨迹压缩算法，用于将曲线抽象成更简单的形状，而不会影响其总体外观。以下是C++实现：

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

using namespace std;

// 定义点结构体
struct Point {
    double x, y;
    Point(double px, double py) : x(px), y(py) {}
};

// 计算点之间的距离
double distance(const Point& p1, const Point& p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}

// 计算点到线段的距离
double perpendicular_distance(const Point& p, const Point& l1, const Point& l2) {
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A*C + B*D;
    double len_sq = C*C + D*D;
    double param = dot / len_sq;

    double xx, yy;

    if (param < 0) {
        xx = l1.x;
        yy = l1.y;
    }
    else if (param > 1) {
        xx = l2.x;
        yy = l2.y;
    }
    else {
        xx = l1.x + param * C;
        yy = l1.y + param * D;
    }

    double dx = p.x - xx;
    double dy = p.y - yy;

    return sqrt(dx*dx + dy*dy);
}

// Douglas-Peucker算法
void douglas_peucker(const vector<Point>& points, double epsilon, vector<Point>& simplified) {
    int n = points.size();
    if (n < 2) return;

    double dmax = 0;
    int index = 0;

    for (int i = 1; i < n-1; ++i) {
        double d = perpendicular_distance(points[i], points[0], points[n-1]);
        if (d > dmax) {
            index = i;
            dmax = d;
        }
    }

    if (dmax > epsilon) {
        vector<Point> left(points.begin(), points.begin()+index+1);
        vector<Point> right(points.begin()+index, points.end());
        vector<Point> left_simplified, right_simplified;
        douglas_peucker(left, epsilon, left_simplified);
        douglas_peucker(right, epsilon, right_simplified);
        simplified.insert(simplified.end(), left_simplified.begin(), left_simplified.end()-1);
        simplified.insert(simplified.end(), right_simplified.begin(), right_simplified.end());
    }
    else {
        simplified.push_back(points[0]);
        simplified.push_back(points[n-1]);
    }
}

// 测试
int main() {
    vector<Point> points = { Point(0,0), Point(0.5,2), Point(1,1), Point(1.5,2), Point(2,0) };
    double epsilon = 0.5;
    vector<Point> simplified_points;
    douglas_peucker(points, epsilon, simplified_points);

    for (auto& p : simplified_points) {
        cout << "(" << p.x << "," << p.y << ") ";
    }
    cout << endl;

    return 0;
}

以上代码实现了Douglas-Peucker算法，将给定的点集压缩成更简单的点集。