曲线降采样之道格拉斯-普克算法Douglas–Peucker

曲线降采样之道格拉斯-普克算法Douglas–Peucker

该算法的目的是,给定一条由线段构成的曲线,找到一条点数较少的相似曲线,来近似描述原始的曲线,达到降低时间、空间复杂度和平滑曲线的目的。

image

附赠自动驾驶学习资料和量产经验:链接

示例(B中红色为降采样后的曲线)

image

算法流程

image

image

image

4. 此时算法已经完成了一个循环,后续按照递归的方式,分别对线段p1-p6和p6-p7进行同样的处理,p6-p7之间的点已经处理完,则直接结束;距离p1-p6线段最远的点为p5,p5到线段距离大于image,则p5也是需要保留的点;

image

image

5. 同理,p5-p6线段之间无待处理点,直接结束;距离p1-p5线段最远的点为p3,其到线段的距离仍大于image,则保留p3;

image

image

6. 距离线段p1-p3最远的点为p2,其距离小于image,将p1到p3中间所有的点标记为忽略;距离线段p3-p5最远的点为p4,其距离也小于image,将p3-p5之间所有待处理点标记为忽略;

7. 至此,算法结束,上述过程中,所有组成线段的端点即为降采样后曲线的点。

时间复杂度

引用:https://zh.wikipedia.org/wiki/%E9%81%93%E6%A0%BC%E6%8B%89%E6%96%AF-%E6%99%AE%E5%85%8B%E7%AE%97%E6%B3%95

image

代码

  • 定义基本结构和工具函数

    // 二维点
    struct Point2D {
    double x;
    double y;
    Point2D() : x(0.0), y(0.0) {}
    Point2D(double x, double y) : x(x), y(y) {}
    };

    // 计算点到线段的距离
    double DouglasPeucker::GetDistanceOnLine(const Point2D &start,
    const Point2D &end,
    const Point2D &point) {
    float a = end.y - start.y;
    float b = start.x - end.x;
    float c = end.x * start.y - start.x * end.y;
    return std::fabs(a * point.x + b * point.y + c) / std::sqrt(a * a + b * b);
    }

  • 核心处理函数

    std::vector
    DouglasPeucker::Process(const std::vector &points_in,
    const double delta) {
    std::vector result;
    // points为需要处理的点集,其中第一个和最后一个点为线段的端点,delta为误差阈值
    // step1. 找到距离线段最远的点
    double max_dist = -1;
    int max_idx = -1;
    // 两头的点默认是保留的, 不需要进行计算
    for (int i = 1; i < points_in.size() - 1; i++) {
    double d = GetDistanceOnLine(points_in[0], points_in[points_in.size() - 1],
    points_in[i]);
    if (d > max_dist) {
    max_dist = d;
    max_idx = i;
    }
    }
    // step2. 如果最远点的距离大于阈值,则将其作为新的线段端点,递归处理
    if (max_dist > delta) {
    std::vector left_pts, right_pts;
    left_pts.reserve(max_idx + 1);
    right_pts.reserve(points_in.size() - max_idx);
    for (int i = 0; i <= max_idx; i++) {
    left_pts.push_back(points_in[i]);
    }
    for (int i = max_idx; i < points_in.size(); i++) {
    right_pts.push_back(points_in[i]);
    }
    std::vector left_result = DouglasPeucker::Process(left_pts, delta);
    std::vector right_result =
    DouglasPeucker::Process(right_pts, delta);
    result.insert(result.end(), left_result.begin(), left_result.end() - 1);
    result.insert(result.end(), right_result.begin(), right_result.end());
    } else { // 两种情况到这里: 点到线段的最大距离小于阈值,或者只有两个点
    result.push_back(points_in[0]);
    result.push_back(points_in[points_in.size() - 1]);
    }
    return result;
    }

  • 运行,将上述p1… p7组成的曲线进行降采样, image

    int main()
    {
    std::vectorAD::Point2D points_in;
    points_in.push_back(AD::Point2D(0.0, 5.0)); // p1
    points_in.push_back(AD::Point2D(1.0, 4.0)); // p2
    points_in.push_back(AD::Point2D(2.0, 3.2)); // p3
    points_in.push_back(AD::Point2D(3.0, 4.5)); // p4
    points_in.push_back(AD::Point2D(4.0, 4.7)); // p5
    points_in.push_back(AD::Point2D(5.0, 1.0)); // p6
    points_in.push_back(AD::Point2D(7.0, 6.0)); // p7
    std::vectorAD::Point2D points_out;
    points_out = AD::DownSampling::DouglasPeucker::Process(points_in, 0.5);
    for (auto &point : points_out) {
    std::cout << "x: " << point.x << ", y: " << point.y << std::endl;
    }

    return 0;
    }

    // 输出
    x: 0, y: 5 // p1
    x: 2, y: 3.2 // p3
    x: 4, y: 4.7 // p5
    x: 5, y: 1 // p6
    x: 7, y: 6 // p7

算法缺点

  • 需要调参,但通常参数也比较好确定;

  • 时间复杂度不稳定;

  • 自顶向下的递归优化,不一定能保证是全局最优,前面做出的选择会影响后续的结果。

相关推荐

  1. 多边形压缩 Douglas-Peucker算法

    2024-04-03 08:40:03       71 阅读
  2. python 算法 鲁斯卡尔算法

    2024-04-03 08:40:03       64 阅读
  3. YOLOv10改进|采用ADown采样模块有效融合

    2024-04-03 08:40:03       35 阅读
  4. PCA算法

    2024-04-03 08:40:03       30 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-03 08:40:03       171 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-03 08:40:03       189 阅读
  3. 在Django里面运行非项目文件

    2024-04-03 08:40:03       157 阅读
  4. Python语言-面向对象

    2024-04-03 08:40:03       170 阅读

热门阅读

  1. 高级排序算法-快速排序

    2024-04-03 08:40:03       46 阅读
  2. Jenkins 自动化更新 Stable Diffusion 介绍

    2024-04-03 08:40:03       40 阅读
  3. maya移除节点 修改节点

    2024-04-03 08:40:03       51 阅读
  4. 上传.PDF文件转为.DOCX文件

    2024-04-03 08:40:03       57 阅读
  5. 音响或耳机音频处理常用的芯片

    2024-04-03 08:40:03       50 阅读
  6. 微信小程序中路由跳转方式

    2024-04-03 08:40:03       48 阅读
  7. Python网络爬虫(二):Requests库

    2024-04-03 08:40:03       40 阅读
  8. SQLAlchemy 的数据库引擎engine与连接对象Connection

    2024-04-03 08:40:03       40 阅读
  9. Knife4j配置使用笔记

    2024-04-03 08:40:03       44 阅读
  10. nodejs的express负载均衡

    2024-04-03 08:40:03       40 阅读
  11. 每天学习一个Linux命令之dpkg

    2024-04-03 08:40:03       45 阅读
  12. linux扩展正则表达式之+

    2024-04-03 08:40:03       41 阅读