18

The qhull library ( qhull.org) has several examples to start in his website, but all the information regarding to the C++ is not very useful to me.

I am trying to make a simple convex Hull of 3D points that I read from a file, I can´t use the technique that is suggested in the website of calling the qhull.exe as an external application because I need to make several convex hull from some modifications that I made in the data points.

I can´t find a simple example for doing this, can someone give me some help in this task? Any information would be useful.

Thanks

Nuno Pessanha Santos
  • 315
  • 2
  • 10

3 Answers3

21

Since I had a hard time using Qhull with c++ myself and couldn't find any useful examples on the web, anddddd have finally succeeded in getting valid results, I'm posting my code here for future use.

This answer works for windows, with visual studio 2012/3. I don't know how or if it works on other platforms

So, to start with things, after downloading qhull source files from here and opening a project in VS, the only files you need to add are the following 2 directories:

libqhull/
libqhullcpp/

After adding these files to your project, add the following code (this is my way, obviously you can use your own way):

Qhull.h

namespace orgQhull{
//...
private:
    PointCoordinates *m_externalPoints;
//...
public:
    void runQhull3D(const std::vector<vec3> &points, const char* args);
    void runQhull(const PointCoordinates &points, const char *qhullCommand2);
//...
}

Qhull.cpp

void Qhull::runQhull3D(const std::vector<vec3> &points, const char* args)
{
    m_externalPoints = new PointCoordinates(3);  //3 = dimension
    vector<double> allPoints;
    for each (vec3 p in points)
    {
        allPoints.push_back(p.x());
        allPoints.push_back(p.y());
        allPoints.push_back(p.z());
    }

    m_externalPoints->append(allPoints); //convert to vector<double>
    runQhull(*m_externalPoints, args);
}

void Qhull::runQhull(const PointCoordinates &points, const char *qhullCommand2)
{
    runQhull(points.comment().c_str(), points.dimension(), points.count(), &*points.coordinates(), qhullCommand2);
}

Finally this is how to use the code:

//not sure all these includes are needed
#include "RboxPoints.h"
#include "QhullError.h"
#include "Qhull.h"
#include "QhullQh.h"
#include "QhullFacet.h"
#include "QhullFacetList.h"
#include "QhullLinkedList.h"
#include "QhullVertex.h"
#include "QhullSet.h"
#include "QhullVertexSet.h"
#include <vector>

int main()
{
    orgQhull::Qhull qhull;
    std::vector<vec3> vertices;
    qhull.runQhull3D(vertices, "Qt");

    QhullFacetList facets = qhull.facetList();
    for (QhullFacetList::iterator it = facets.begin(); it != facets.end(); ++it)
    {
        if (!(*it).isGood()) continue;
        QhullFacet f = *it;
        QhullVertexSet vSet = f.vertices();
        for (QhullVertexSet::iterator vIt = vSet.begin(); vIt != vSet.end(); ++vIt)
        {
            QhullVertex v = *vIt;
            QhullPoint p = v.point();
            double * coords = p.coordinates();
            vec3 aPoint = vec3(coords[0], coords[1], coords[2]);
            // ...Do what ever you want
        }
    }
    
    // Another way to iterate (c++11), and the way the get the normals
    std::vector<std::pair<vec3, double> > facetsNormals;
    for each (QhullFacet facet : qhull.facetList().toStdVector())
    {
        if (facet.hyperplane().isDefined())
        {
            auto coord = facet.hyperplane().coordinates();
            vec3 normal(coord[0], coord[1], coord[2]);
            double offset = facet.hyperplane().offset();
            facetsNormals.push_back(std::pair<vec3, double>(normal, offset));
        }
    }
}

Note that I copied this code from my project and have modified it a bit to be more informative but haven't compiled this example.

ZivS
  • 2,094
  • 2
  • 27
  • 48
  • @Raaj thanks for pointing it out for others. Feel free to edit my answer with a thread safe code and I'll review and accept it – ZivS Feb 23 '17 at 11:57
  • There isn't. I've looked through the whole internet/github/codeproject everything. There is no C/C++ example of a Convex/Concave hull algorithm. – Raaj Feb 24 '17 at 02:55
  • If im not wrong..qhull has come up with this new re-entrant qhull that is thread safe. I've not found any examples of using that code – Raaj Feb 25 '17 at 08:19
  • 1
    qhull 2015 is re-entrant but not thread safe: see http://www.qhull.org/html/qh-code.htm#reentrant and http://www.qhull.org/html/qh-code.htm#cpp – Gnat May 26 '17 at 01:26
  • 1
    Thank you, this post really was useful. – stephanmg Jun 19 '18 at 14:59
  • Great answer! Do you know why it can happen that the normal (in 3 dimensions) is `(nan, nan, nan)`? I guess this is what the function `facet.hyperplane.isDefined()` refers to? – katherinejohnson Aug 26 '22 at 09:54
1

Here is an simple example using re-entrant qhull from c++. I think it might be useful.

#include <iostream>
#include <vector>
#include <string>

#include "Qhull.h"

int main(int argc, char const *argv[])
{

    std::vector<double> points_3D = {0, 0, 0,
                                     0, 1, 0,
                                     1, 1, 0,
                                     1, 0, 0,
                                     0, 0, 1,
                                     0, 1, 1,
                                     1, 1, 1,
                                     1, 0, 1};

    int ndim = 3;
    int num_points = points_3D.size() / ndim;

    std::string comment = ""; // rbox commands, see http://www.qhull.org/html/rbox.htm
    std::string qhull_command = ""; // For qhull commands, see http://www.qhull.org/html/qhull.htm

    try
    {
        orgQhull::Qhull qhull = orgQhull::Qhull(comment.c_str(), ndim, num_points, points_3D.data(), qhull_command.c_str());
        std::cout << "qhull.hullDimension(): " << qhull.hullDimension() << "\n";
        std::cout << "qhull.volume(): " << qhull.volume() << "\n";
        std::cout << "qhull.area(): " << qhull.area() << "\n";
    }
    catch (orgQhull::QhullError &e)
    {
        std::cerr << e.what() << std::endl;
        return e.errorCode();
    }
}
rtclark
  • 555
  • 4
  • 16
1

This post had the only examples I could find of qHull so I wanted to add this snippet of code for how to get the convex hull of a 2D set of points using qhull.

#include <vector>

#include "my_point.h"
#include "libqhullcpp/Qhull.h"
#include "libqhullcpp/QhullVertex.h"
#include "libqhullcpp/QhullVertexSet.h"
#include "libqhullcpp/QhullPoint.h"

std::vector<my_point> getConvexHull2D(const std::vector<my_point> &scatteredPoints)
{
  std::vector<my_point> cHull;
  if(scatteredPoints.size() < 3) return cHull;

  std::vector<double> inputVertices;
  for(int i = 0; i < (int)scatteredPoints.size(); i++)
  {
    const my_point &pt = scatteredPoints[i];
    inputVertices.push_back(pt.x);
    inputVertices.push_back(pt.y);
  }

  orgQhull::Qhull qhull;

  int ndim = 2;
  int num_points = inputVertices.size() / ndim;
  const char *inputComments = "";
  const char *qHullCommands = "";

  qhull.runQhull(inputComments, ndim, num_points, inputVertices.data(), qHullCommands);

  for(const orgQhull::QhullVertex &v: qhull.vertexList())
  {
    const orgQhull::QhullPoint &qhullPt = v.point();
    auto coords = qhullPt.coordinates(); // list of doubles
    cHull.push_back(my_point(coords[0], coords[1]));
  }

  // the vertices are not sorted?
  CCWSort(cHull.data(), cHull.size());
  return cHull;
}

I also had to build the libraries and link qhullcpp.lib and qhullstatic_r.lib in addition to adding qhull/src to the include path. There is a Qt project included that you can open and build which will build the libs for you.

I tried to use boost first but it was conflicting too much with some legacy code. This might not be the most efficient implementation, but it's much better than what I had previously.

Ahmed Hassanin
  • 11
  • 2