Skip to content

Header-only single-class implementation of Quickhull algorithm for convex hulls finding in arbitrary dimension (>1) space.

Notifications You must be signed in to change notification settings

tomilov/quickhull

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

NOTE: This library is header-only.

Implementation of the Quickhull algorithm (Barber et al) for the convex hulls finding in arbitrary dimension (>1) space. Also implemented the Mehlhorn algorithm (Mehlhorn et al) for checking convexity of resulting geometric structure.

Example:

#include <quickhull.hpp>

#include <array>
#include <iterator>
#include <limits>
#include <random>
#include <vector>

#include <cstdlib>

int main()
{
    using F = float;
    constexpr std::size_t dim = 3;
    using Points = std::vector<std::array<F, dim>>;

    Points points(10); // input

    { // fill it somehow (use real data)
        std::mt19937 gen;
        for (auto & [x, y, z] : points) {
            x = std::generate_canonical<F, std::numeric_limits<F>::digits>(gen);
            y = std::generate_canonical<F, std::numeric_limits<F>::digits>(gen);
            z = std::generate_canonical<F, std::numeric_limits<F>::digits>(gen);
        }
    }

    const auto eps = std::numeric_limits<F>::epsilon();
    quick_hull<typename Points::const_iterator> qh{dim, eps};
    qh.add_points(std::cbegin(points), std::cend(points));
    auto initial_simplex = qh.get_affine_basis();
    if (initial_simplex.size() < dim + 1) {
        return EXIT_FAILURE; // degenerated input set
    }
    qh.create_initial_simplex(std::cbegin(initial_simplex), std::prev(std::cend(initial_simplex)));
    qh.create_convex_hull();
    if (!qh.check()) {
        return EXIT_FAILURE; // resulted structure is not convex (generally due to precision errors)
    }

    qh.facets_; // use as result
}