ConcaveHull/CONCAVEHull
凸包和凹包的区别如下图所示。
对于给定的一组点云集合，对应的凸包是唯一确定的。但凹包解不唯一。
算法流程
凹包计算
在给定投影平面上，使用一个半径为α的圆进行滚动。当α足够大时这个圆只会陷进去但不会进入到点云空间内部。其滚动的路线就是对应点云的凹包。
- 将点云投影到平面，得到二维点集 P。
- 定义一个圆（滚球），其半径为 alpha。
- 从点集 P 中任选一个种子点 \(p_i\)，计算 \(p_i\) 与点集 P 中各点之间的距离，并将所有与 \(p_i\) 距离小于 \(2 \times \text{alpha}\) 的点加入点集 Q，作为初始候选边界点集。
- 从点集 Q 中任选一个种子点 \(q_i\)，构造同时经过 \(p_i\) 和 \(q_i\) 且半径为 alpha 的两个外接圆 \(C_{p_i}) 和 (C_{q_i}\)。
- 判断外接圆 \(C_{p_i}\) 和 \(C_{q_i}\)，若其中任意一个圆内不存在点集 P 中的其他点（即 \(p_i\) 与 \(q_i\) 可被同一个滚球覆盖），则连接 \(p_i\) 与 \(q_i\)，作为凹包的一条边。
- 对点集 Q 中的所有点，依次执行步骤 4 和步骤 5，直至点集 Q 中的所有点均被处理。
- 对点集 P 中的所有点，依次执行步骤 3 至步骤 6，直至点集 P 中的所有点均被处理。
- 将所有生成的连接边组合，形成最终的凹包。
凸包计算
凸包的计算类似于二维平面上的Delaunay三角化，只不过PCL中的三维点云凸包拟合，是四个点初始化一个四面体。
-
从点云中任选四个不共面的点，构造一个初始凸包（四面体），并将其顶点集合记为 D。
-
遍历点云中的所有点。对每个点 P，采用射线法判断其相对于当前凸包的位置关系：
1）若点 P 位于凸包内部，则跳过；
2）若点 P 位于凸包外部，则将点 P 加入点集 D，并基于更新后的点集重新计算凸包；随后删除点集 D 中不属于凸包顶点的点，得到新的点集 D。 -
当所有点遍历完成后，当前凸多面体即为点云的三维凸包。
在PCL中计算凹包必须先将所有点投影到一个统一平面上才行，对于凹包则不做要求。
使用示例
pcl::ModelCoefficients::Ptr coefficients(new pcl::ModelCoefficients);
pcl::PointIndices::Ptr inliers(new pcl::PointIndices);
// 分割点
pcl::SACSegmentation<pcl::PointXYZ> seg;
// Optional
seg.setOptimizeCoefficients(true);
// Mandatory
seg.setModelType(pcl::SACMODEL_PLANE);
seg.setMethodType(pcl::SAC_RANSAC);
seg.setDistanceThreshold(0.01);seg.setInputCloud(cloud_filtered);
seg.segment(*inliers, *coefficients);
std::cerr << "PointCloud after segmentation has: "<< inliers->indices.size() << " inliers." << std::endl;// 投影分离出的点 到对应的平面模型
pcl::ProjectInliers<pcl::PointXYZ> proj;
proj.setModelType(pcl::SACMODEL_PLANE);
// proj.setIndices (inliers);
proj.setInputCloud(cloud_filtered);
proj.setModelCoefficients(coefficients);
proj.filter(*cloud_projected);
std::cerr << "PointCloud after projection has: "<< cloud_projected->size() << " data points." << std::endl;// 为投影后的点 创建凹包
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_hull(new pcl::PointCloud<pcl::PointXYZ>);
pcl::ConcaveHull<pcl::PointXYZ> chull;
chull.setInputCloud(cloud_projected);
chull.setAlpha(0.1);
chull.reconstruct(*cloud_hull);
在PCL中如果向计算凸包把所有的Concave换成Convex即可。