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

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

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

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

示例（B中红色为降采样后的曲线）

算法流程

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

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

6. 距离线段p1-p3最远的点为p2，其距离小于，将p1到p3中间所有的点标记为忽略；距离线段p3-p5最远的点为p4，其距离也小于，将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

代码

定义基本结构和工具函数

// 二维点
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组成的曲线进行降采样，

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