CODEWITHSUNDEEP
c++algorithmconvex-hull
Am1rr3zA
Am1rr3zA

Reputation: 7411

C++ ConvexHull of points algorithm (and their indices)

I need to implement a C++ code that computes a ConvexHull of points and returns the indices, I couldn't find a way to do it in C++?

in Matlab and Python it's very easy you just need to pass an array of points to ConvexHull function and it returns the indices; do we have something equivalent in c++?

Upvotes: 1

Views: 2276

Answers (2)

emilyfy
emilyfy

Reputation: 313

I needed to get the convex hull indices for point clouds in C++ and was also annoyed by the fact that the functions provided by PCL or Boost don't return the indices of the points. And you're right that the QHull documentation seems quite complicated. So I went to look at the PCL source codes and extract it myself. Here's what I got

extern "C"
{
    #include <qhull/qhull.h>
}

pcl::PointCloud<pcl::PointXYZ>::Ptr cloud; // some point cloud
int dimension = 2, size = cloud->size();
coordT* points = reinterpret_cast<coordT*> (calloc (size*dimension, sizeof(coordT)));
for (size_t i=0; i<size; ++i)
{
    points[2*i] = static_cast<coordT> (cloud->points[i].x);
    points[2*i+1] = static_cast<coordT> (cloud->points[i].y);
}
int exitcode = qh_new_qhull(dimension, size, points, true, const_cast<char*> ("qhull FA"), NULL, NULL);
if (exitcode != 0 || qh num_vertices == 0)
{
    std::cerr << "ERROR: qhull was unable to compute a convex hull for the given point cloud" << std::endl;
}
pcl::PointIndices::Ptr hull_indices (new pcl::PointIndices());
vertexT * vertex;
FORALLvertices
{
    hull_indices->indices.push_back(qh_pointid(vertex->point));
}
qh_freeqhull(!qh_ALL);
int curlong, totlong;
qh_memfreeshort(&curlong, &totlong);

Note that this is for 2D point clouds. For other dimensions or data types, you can modify it accordingly. Hope that helps!

Upvotes: 1

Throwback1986
Throwback1986

Reputation: 5995

QHull is the defacto standard for convex hulls, Delaunay triangulations, and friends. QHull offers a number of languages and interfaces - plus the page links to some very good references.

Upvotes: 0

Related Questions