目录
取点云的凹边界是计算几何中的一个经典问题。凹边界与凸边界不同，它能捕捉到数据的细节和凹形结构。在点云处理中，凹边界提取用于描述点云的外形。以下是关于凹边界提取的详细介绍：
1 原理介绍
凹边界提取的基本思想是找到一个边界，该边界可以包围点云中的所有点，同时允许凹陷，以更紧密地拟合点云的形状。凹边界的计算通常基于一个参数，该参数决定了边界的细节程度。常用的方法包括 α-球体（α-shape）方法。
α-shape 的基础概念
-
Delaunay 三角剖分: 给定一个点集，Delaunay 三角剖分是该点集的一个三角剖分，其特点是任何一个三角形的外接圆的内部不包含其他点。Delaunay 三角剖分是构建 α-shape 的基础。
-
α-ball: α-ball 是指半径为 α 的球体。在二维情况下，这个球体是一个圆。在 α-shape 方法中，我们使用 α-ball 来确定哪些边和面（在三维中）属于 α-shape。
-
α-shape: 对于给定的点集和 α 值，α-shape 是由 Delaunay 三角剖分中的一部分边和面构成的多边形或多面体。具体而言，如果一个三角形的外接圆半径小于 α，则该三角形在 α-shape 中被保留。
数学公式推导
2.1 外接圆半径
给定一个三角形，其顶点为 A(x1,y1), B(x2,y2), C(x3,y3)，我们可以计算三角形的三条边的长度：
外接圆半径 R 可以通过三角形的边长及其面积来计算。公式如下：
其中 a,b,c 是三角形的三条边的长度，A 是三角形的面积，计算方法如下：
是三角形的半周长
2.2 根据 α 参数筛选三角形
-
α 参数: 这是一个用户定义的参数，控制 α-shape 的细节程度。α 值越小，保留的细节越多。
-
筛选过程:
- 遍历 Delaunay 三角剖分中的每个三角形。
- 如果三角形的外接圆半径小于或等于 α，则保留该三角形；否则，去除。
-
结果: 通过这种筛选，我们将只保留那些满足 α 条件的三角形或四面体，它们构成 α-shape 的基本单元。
2.3 构建 α-shape
-
连接: 将保留的三角形或四面体连接起来构成一个多边形或多面体，即 α-shape。
-
拓扑结构: 保证这些单元之间的拓扑连接性，以形成一个封闭的形状。
2.4 参数调整与优化
-
α 参数调整: 根据具体需求调整 α 值，观察 α-shape 的变化。较小的 α 值可能生成更复杂的形状，而较大的 α 值则更接近于凸包。
-
优化: 通过优化算法或启发式方法找到最佳 α 值，使得生成的 α-shape 能够最准确地描述点集的结构。
3 α-shape 的构建步骤
-
计算 Delaunay 三角剖分: Delaunay 三角剖分的性质是对于任意一个三角形，其外接圆内不包含任何其他点。这一性质使得 Delaunay 三角剖分在构建 α-shape 时非常有效，因为我们可以通过简单地遍历三角形并计算其外接圆半径来决定是否保留这个三角形。
-
计算外接圆半径: 对于 Delaunay 三角剖分中的每个三角形，计算其外接圆半径 R。
-
筛选三角形: 遍历所有的三角形，保留那些外接圆半径 R≤α 的三角形。这是因为较小的 α 值会去除那些包含较多空洞的三角形，而较大的 α 值会保留更多的细节。
-
生成 α-shape: 使用保留下来的三角形生成 α-shape，即为最终的凹边界。
4 示例代码
#include <pcl/point_types.h>
#include <pcl/point_cloud.h>
#include <pcl/surface/concave_hull.h>
#include <pcl/io/ply_io.h>
#include <pcl/io/pcd_io.h>
#include <pcl/visualization/pcl_visualizer.h>
#include <pcl/geometry/planar_polygon.h>
int main() {
// 创建点云对象并加载数据
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
if (pcl::io::loadPCDFile<pcl::PointXYZ>("cloud1.pcd", *cloud) == -1) {
PCL_ERROR("Couldn't read file input.pcd\n");
return -1;
}
// 创建 ConcaveHull 对象并设置参数
pcl::ConcaveHull<pcl::PointXYZ> concave_hull;
concave_hull.setInputCloud(cloud);
concave_hull.setAlpha(0.5); // 设置 alpha 值，0.1 是一个经验值
// 计算凹边界
pcl::PointCloud<pcl::PointXYZ>::Ptr hull(new pcl::PointCloud<pcl::PointXYZ>);
std::vector<pcl::Vertices> polygons;
concave_hull.reconstruct(*hull, polygons);
// 初始化可视化器
pcl::visualization::PCLVisualizer::Ptr viewer(new pcl::visualization::PCLVisualizer("3D Viewer"));
viewer->setBackgroundColor(0, 0, 0);
// 添加点云和凹边界到可视化器
pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> cloud_color(cloud, 255, 255, 255);
viewer->addPointCloud<pcl::PointXYZ>(cloud, cloud_color, "original cloud");
pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> hull_color(hull, 255, 255, 0);
viewer->addPointCloud<pcl::PointXYZ>(hull, hull_color, "concave hull");
pcl::PointCloud<pcl::PointXYZ>::Ptr polygon_points(new pcl::PointCloud<pcl::PointXYZ>);
// 添加多边形
for (const auto& polygon : polygons) {
for (const auto& idx : polygon.vertices) {
polygon_points->points.push_back(hull->points[idx]);
}
}
pcl::PlanarPolygon<pcl::PointXYZ> polygon;
polygon.setContour(*polygon_points);
viewer->addPolygon(polygon, 255.0, 0, 0, "polygon");
// 设置点云属性
viewer->setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 2, "original cloud");
viewer->setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 5, "concave hull");
// 主循环
while (!viewer->wasStopped()) {
viewer->spinOnce(0);
}
return 0;
}
