# Application of 3D Convex Hull Algorithm in PCL

Given n vertices in three-dimensional space, solve the convex hull surface formed by these n vertices.
Solving process:
First choose a tetrahedron (initial convex hull) formed by 4 points, and then add a new point P each time, in two cases:
1. If P is in the convex hull, it can be skipped
2. P is outside the convex hull. For a certain edge, find the surface S that contains the edge that can be "visible" from this point (can you see if it can be calculated by the normal vector, see if the point is outside the surface), delete these surfaces S, Then use the other two sides of S except this side and point P to form two new faces. By traversing all edges in this way, P is added to the convex hull and a new convex hull is formed.
Traverse all points, and finally get the convex hull of the entire point set.
Reference article:
3D convex hull
Get the convex hull of a point cloud model in pcl:

```#include <pcl/ModelCoefficients.h>
#include <pcl/point_types.h>
#include <pcl/io/pcd_io.h>
#include <pcl/surface/convex_hull.h>
#include <pcl\visualization\pcl_visualizer.h>
using namespace pcl::console;

int
main(int argc, char** argv)
{
// Read in the cloud data
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>), cloud_f(new pcl::PointCloud<pcl::PointXYZ>);
std::cout << "PointCloud before filtering has: " << cloud->points.size() << " data points." << std::endl; //*

pcl::ConvexHull<pcl::PointXYZ> hull;
hull.setInputCloud(cloud);
hull.setDimension(3);

std::vector<pcl::Vertices> polygons;
pcl::PointCloud<pcl::PointXYZ>::Ptr surface_hull(new pcl::PointCloud<pcl::PointXYZ>);
hull.reconstruct(*surface_hull, polygons);

cout << surface_hull->size() ;

// ---------------------- Visualizer -------------------------------------------
boost::shared_ptr<pcl::visualization::PCLVisualizer> viewer(new pcl::visualization::PCLVisualizer);
viewer->setBackgroundColor(255, 255, 255);

pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> color_handler(cloud, 255, 255, 0);
viewer->setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 6, "sample cloud");

pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> color_handlerK(surface_hull, 255, 0, 0);
viewer->setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 6, "point");

while (!viewer->wasStopped())
{
viewer->spinOnce(100);
}

return (0);
}

```

operation result:
The visualization of the convex hull points (red) of the point cloud is as follows:

Uncomment the first line to connect the convex hull points in order:
Visualize the result:

Observe that there are many lines going through the interior of the rabbit, this method does not display the convex hull correctly.
Uncomment the second line of code to visualize the result:

This correctly shows the convex hull of the 3D model.

Reference article:
PCL reconstructs the convex hull of the point cloud and displays it

Posted by saiko on Wed, 25 May 2022 16:16:45 +0300