目录一、弦差法1、核心定义2、算法流程3、适用场景4、参考文献二、代码实现三、结果展示一、弦差法弦差法的核心思想是通过最大的点间距离和最大的偏差值形成一个柱形管道来筛选点云数据。在实际应用中主要有两种实现维度其目的都是为了在大幅减少数据量的同时最大程度保留物体的几何轮廓和细节特征。1、核心定义构建弦Chord假设点云已经按照空间位置如X轴或轨迹方向进行了排序。对于有序点序列P 1 , P 2 , . . . , P n P_1, P_2, ..., P_nP1,P2,...,Pn相邻的两个点如P 1 P_1P1和P 3 P_3P3之间的连线或者相邻线段如P 1 P 2 P_1P_2P1P2和P 2 P 3 P_2P_3P2P3构成了“弦”。最大点间距离弦长控制相邻保留点之间的最大空间间隔。如果两点距离过大说明该处曲率变化剧烈或是边缘必须保留该点以维持形状。最大偏差值弦高对于当前待判定的点P i P_iPi连接其前后的点P i − 1 P_{i-1}Pi−1和P i 1 P_{i1}Pi1形成一条直线弦。计算点P i P_iPi到这条弦的垂直距离这个距离就是“弦高”或“偏差值”。2、算法流程算法通常采用迭代贪婪的方式进行筛选具体步骤如下初始化保留点云序列的第一个点和最后一个点这两个点是必须保留的锚点。寻找最大偏差点遍历当前未被判定保留的点集计算每个点到其对应弦的垂直距离弦高。筛选判断找出所有点中弦高最大的那个点。如果该最大弦高大于设定的阈值ϵ \epsilonϵ即超出了“柱形管道”的允许偏差范围则强制保留该点。如果该最大弦高小于阈值说明该区域内的点非常平直处于“柱形管道”内则可以安全地舍弃该点或者只保留端点。递归迭代以被保留的点为新的分割点将剩余的点云划分为左右两个子区间重复步骤2和步骤3直到所有区间都处理完毕。3、适用场景经典的弦差法最擅长处理有序点云如一维扫描线、边界轮廓线。对于完全散乱的点云通常需要先使用切片Slicing或投影技术将其转化为有序序列然后再应用弦差法。弦差法与道格拉斯普客算法本质上是同一套数学逻辑不同领域的叫法。两者都是首尾连线 → 算最大垂距弦高→ 与阈值比 → 超阈值则保留并递归分裂这一套流程。 DP 算法 1972 年由 Urs Ramer 提出、1973 年 Douglas Peucker 完善最早用于地图制图综合点云圈的弦差法 / 弦高差法是把同一套逻辑搬到三维点列上换了个更直观的名字——弦就是首尾连线差就是这个垂距。虽然骨架一样但弦差法在点云语境下通常会多做一两件事维度Douglas-Peucker经典版弦差法点云语境起源领域GIS、制图、轨迹压缩二维折线点云抽稀、多波束测深、激光扫描线维度主要是 2Dx,y或 (lon,lat)扩展到 3Dx,y,z阈值单一 ε垂距/弦高常双阈值ε弦高 最大点间距防长距离跨越有序性要求必须是有序点列同左但点云常先切片/投影/按扫描线排序才用常见改良原始 DP角度-弦高联合准则、点云离散度二次抽稀等4、参考文献[1]周正鋆. 隧道点云数据的配准方法研究[D]. 东华理工大学, 2014.二、代码实现#includeiostream#includevector#includealgorithm#includecmath#includepcl/io/pcd_io.h#includepcl/point_types.h#includepcl/visualization/pcl_visualizer.h// 计算点P到直线AB的垂直距离doubleperpendicularDistance(constpcl::PointXYZA,constpcl::PointXYZB,constpcl::PointXYZP){doubledxB.x-A.x,dyB.y-A.y,dzB.z-A.z;doublelenstd::sqrt(dx*dxdy*dydz*dz);if(len1e-12)return0.0;// 叉积模长 / 向量长度doublecross_xdy*(P.z-A.z)-dz*(P.y-A.y);doublecross_ydz*(P.x-A.x)-dx*(P.z-A.z);doublecross_zdx*(P.y-A.y)-dy*(P.x-A.x);returnstd::sqrt(cross_x*cross_xcross_y*cross_ycross_z*cross_z)/len;}// 递归简化Douglas-PeuckervoidsimplifyRecursive(conststd::vectorpcl::PointXYZpts,intstart,intend,doublechord_threshold,doublemax_seg_len,std::vectorboolkept){if(end-start1)return;// 检查首尾距离是否超过最大线段长度doubleseg_lenstd::sqrt(std::pow(pts[end].x-pts[start].x,2)std::pow(pts[end].y-pts[start].y,2)std::pow(pts[end].z-pts[start].z,2));if(seg_lenmax_seg_len){// 强制保留中间点取中点索引intmid(startend)/2;kept[mid]true;simplifyRecursive(pts,start,mid,chord_threshold,max_seg_len,kept);simplifyRecursive(pts,mid,end,chord_threshold,max_seg_len,kept);return;}// 找最大弦高点intmaxIdxstart;doublemaxDist0.0;for(intistart1;iend;i){doubledperpendicularDistance(pts[start],pts[end],pts[i]);if(dmaxDist){maxDistd;maxIdxi;}}if(maxDistchord_threshold){kept[maxIdx]true;simplifyRecursive(pts,start,maxIdx,chord_threshold,max_seg_len,kept);simplifyRecursive(pts,maxIdx,end,chord_threshold,max_seg_len,kept);}// 否则不做任何事中间点全部丢弃}pcl::PointCloudpcl::PointXYZchordalSimplify(constpcl::PointCloudpcl::PointXYZcloud,doublechord_threshold,doublemax_seg_len){if(cloud.empty())returnpcl::PointCloudpcl::PointXYZ();std::vectorpcl::PointXYZpts(cloud.begin(),cloud.end());intnpts.size();std::vectorboolkept(n,false);kept[0]kept[n-1]true;// 首尾必保simplifyRecursive(pts,0,n-1,chord_threshold,max_seg_len,kept);pcl::PointCloudpcl::PointXYZout;out.reserve(std::count(kept.begin(),kept.end(),true));for(inti0;in;i){if(kept[i])out.push_back(pts[i]);}returnout;}intmain(){// 读取点云pcl::PointCloudpcl::PointXYZ::Ptrcloud(newpcl::PointCloudpcl::PointXYZ);if(pcl::io::loadPCDFilepcl::PointXYZ(sorted_cloud.pcd,*cloud)-1){std::cerr错误无法读取点云文件std::endl;return-1;}std::cout原始点数: cloud-size()std::endl;// 参数设置根据实际情况调整doublechord_thresh0.05;// 弦高阈值米doublemax_seg_len0.5;// 最大线段长度米pcl::PointCloudpcl::PointXYZsimplifiedchordalSimplify(*cloud,chord_thresh,max_seg_len);std::cout简化后点数: simplified.size()std::endl;std::cout简化比例: (double)simplified.size()/cloud-size()*100%std::endl;// 保存结果pcl::io::savePCDFileBinary(simplified_chordal.pcd,simplified);std::cout结果已保存至 simplified_chordal.pcdstd::endl;// 可视化对比pcl::visualization::PCLVisualizerviewer(u8弦差法简化);viewer.addPointCloudpcl::PointXYZ(cloud,original);viewer.setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_COLOR,1.0,0.0,0.0,original);viewer.addPointCloudpcl::PointXYZ(simplified.makeShared(),simplified);viewer.setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_COLOR,0.0,1.0,0.0,simplified);viewer.spin();return0;}参数调优threshold_弦高阈值是核心参数。阈值越大简化程度越高丢失的细节越多阈值越小保留的点越多计算量越大。建议根据点云的平均点间距mean_distance来设定通常为0.1 ~ 0.5倍的平均间距。三、结果展示
PCL 弦差法实现点云精简
目录一、弦差法1、核心定义2、算法流程3、适用场景4、参考文献二、代码实现三、结果展示一、弦差法弦差法的核心思想是通过最大的点间距离和最大的偏差值形成一个柱形管道来筛选点云数据。在实际应用中主要有两种实现维度其目的都是为了在大幅减少数据量的同时最大程度保留物体的几何轮廓和细节特征。1、核心定义构建弦Chord假设点云已经按照空间位置如X轴或轨迹方向进行了排序。对于有序点序列P 1 , P 2 , . . . , P n P_1, P_2, ..., P_nP1,P2,...,Pn相邻的两个点如P 1 P_1P1和P 3 P_3P3之间的连线或者相邻线段如P 1 P 2 P_1P_2P1P2和P 2 P 3 P_2P_3P2P3构成了“弦”。最大点间距离弦长控制相邻保留点之间的最大空间间隔。如果两点距离过大说明该处曲率变化剧烈或是边缘必须保留该点以维持形状。最大偏差值弦高对于当前待判定的点P i P_iPi连接其前后的点P i − 1 P_{i-1}Pi−1和P i 1 P_{i1}Pi1形成一条直线弦。计算点P i P_iPi到这条弦的垂直距离这个距离就是“弦高”或“偏差值”。2、算法流程算法通常采用迭代贪婪的方式进行筛选具体步骤如下初始化保留点云序列的第一个点和最后一个点这两个点是必须保留的锚点。寻找最大偏差点遍历当前未被判定保留的点集计算每个点到其对应弦的垂直距离弦高。筛选判断找出所有点中弦高最大的那个点。如果该最大弦高大于设定的阈值ϵ \epsilonϵ即超出了“柱形管道”的允许偏差范围则强制保留该点。如果该最大弦高小于阈值说明该区域内的点非常平直处于“柱形管道”内则可以安全地舍弃该点或者只保留端点。递归迭代以被保留的点为新的分割点将剩余的点云划分为左右两个子区间重复步骤2和步骤3直到所有区间都处理完毕。3、适用场景经典的弦差法最擅长处理有序点云如一维扫描线、边界轮廓线。对于完全散乱的点云通常需要先使用切片Slicing或投影技术将其转化为有序序列然后再应用弦差法。弦差法与道格拉斯普客算法本质上是同一套数学逻辑不同领域的叫法。两者都是首尾连线 → 算最大垂距弦高→ 与阈值比 → 超阈值则保留并递归分裂这一套流程。 DP 算法 1972 年由 Urs Ramer 提出、1973 年 Douglas Peucker 完善最早用于地图制图综合点云圈的弦差法 / 弦高差法是把同一套逻辑搬到三维点列上换了个更直观的名字——弦就是首尾连线差就是这个垂距。虽然骨架一样但弦差法在点云语境下通常会多做一两件事维度Douglas-Peucker经典版弦差法点云语境起源领域GIS、制图、轨迹压缩二维折线点云抽稀、多波束测深、激光扫描线维度主要是 2Dx,y或 (lon,lat)扩展到 3Dx,y,z阈值单一 ε垂距/弦高常双阈值ε弦高 最大点间距防长距离跨越有序性要求必须是有序点列同左但点云常先切片/投影/按扫描线排序才用常见改良原始 DP角度-弦高联合准则、点云离散度二次抽稀等4、参考文献[1]周正鋆. 隧道点云数据的配准方法研究[D]. 东华理工大学, 2014.二、代码实现#includeiostream#includevector#includealgorithm#includecmath#includepcl/io/pcd_io.h#includepcl/point_types.h#includepcl/visualization/pcl_visualizer.h// 计算点P到直线AB的垂直距离doubleperpendicularDistance(constpcl::PointXYZA,constpcl::PointXYZB,constpcl::PointXYZP){doubledxB.x-A.x,dyB.y-A.y,dzB.z-A.z;doublelenstd::sqrt(dx*dxdy*dydz*dz);if(len1e-12)return0.0;// 叉积模长 / 向量长度doublecross_xdy*(P.z-A.z)-dz*(P.y-A.y);doublecross_ydz*(P.x-A.x)-dx*(P.z-A.z);doublecross_zdx*(P.y-A.y)-dy*(P.x-A.x);returnstd::sqrt(cross_x*cross_xcross_y*cross_ycross_z*cross_z)/len;}// 递归简化Douglas-PeuckervoidsimplifyRecursive(conststd::vectorpcl::PointXYZpts,intstart,intend,doublechord_threshold,doublemax_seg_len,std::vectorboolkept){if(end-start1)return;// 检查首尾距离是否超过最大线段长度doubleseg_lenstd::sqrt(std::pow(pts[end].x-pts[start].x,2)std::pow(pts[end].y-pts[start].y,2)std::pow(pts[end].z-pts[start].z,2));if(seg_lenmax_seg_len){// 强制保留中间点取中点索引intmid(startend)/2;kept[mid]true;simplifyRecursive(pts,start,mid,chord_threshold,max_seg_len,kept);simplifyRecursive(pts,mid,end,chord_threshold,max_seg_len,kept);return;}// 找最大弦高点intmaxIdxstart;doublemaxDist0.0;for(intistart1;iend;i){doubledperpendicularDistance(pts[start],pts[end],pts[i]);if(dmaxDist){maxDistd;maxIdxi;}}if(maxDistchord_threshold){kept[maxIdx]true;simplifyRecursive(pts,start,maxIdx,chord_threshold,max_seg_len,kept);simplifyRecursive(pts,maxIdx,end,chord_threshold,max_seg_len,kept);}// 否则不做任何事中间点全部丢弃}pcl::PointCloudpcl::PointXYZchordalSimplify(constpcl::PointCloudpcl::PointXYZcloud,doublechord_threshold,doublemax_seg_len){if(cloud.empty())returnpcl::PointCloudpcl::PointXYZ();std::vectorpcl::PointXYZpts(cloud.begin(),cloud.end());intnpts.size();std::vectorboolkept(n,false);kept[0]kept[n-1]true;// 首尾必保simplifyRecursive(pts,0,n-1,chord_threshold,max_seg_len,kept);pcl::PointCloudpcl::PointXYZout;out.reserve(std::count(kept.begin(),kept.end(),true));for(inti0;in;i){if(kept[i])out.push_back(pts[i]);}returnout;}intmain(){// 读取点云pcl::PointCloudpcl::PointXYZ::Ptrcloud(newpcl::PointCloudpcl::PointXYZ);if(pcl::io::loadPCDFilepcl::PointXYZ(sorted_cloud.pcd,*cloud)-1){std::cerr错误无法读取点云文件std::endl;return-1;}std::cout原始点数: cloud-size()std::endl;// 参数设置根据实际情况调整doublechord_thresh0.05;// 弦高阈值米doublemax_seg_len0.5;// 最大线段长度米pcl::PointCloudpcl::PointXYZsimplifiedchordalSimplify(*cloud,chord_thresh,max_seg_len);std::cout简化后点数: simplified.size()std::endl;std::cout简化比例: (double)simplified.size()/cloud-size()*100%std::endl;// 保存结果pcl::io::savePCDFileBinary(simplified_chordal.pcd,simplified);std::cout结果已保存至 simplified_chordal.pcdstd::endl;// 可视化对比pcl::visualization::PCLVisualizerviewer(u8弦差法简化);viewer.addPointCloudpcl::PointXYZ(cloud,original);viewer.setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_COLOR,1.0,0.0,0.0,original);viewer.addPointCloudpcl::PointXYZ(simplified.makeShared(),simplified);viewer.setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_COLOR,0.0,1.0,0.0,simplified);viewer.spin();return0;}参数调优threshold_弦高阈值是核心参数。阈值越大简化程度越高丢失的细节越多阈值越小保留的点越多计算量越大。建议根据点云的平均点间距mean_distance来设定通常为0.1 ~ 0.5倍的平均间距。三、结果展示
