Convex Hull Algorithms in C++14

This small library provides a mono-threaded implementation for Graham Scan, Monotone Chain, Jarvis March and Chan's algorithms for the computation of the convex hull of a set of points in the 2D space.

Build prerequisites

The implementation is written in C++14 and requires a fully conformant C++14 compiler. Some features of C++17 are also used, but C++17 is not very different from C++14 so it should be easy to backport to C++14 if required.

The code compiles and runs successfully with clang-900.0.37 on Mac OS X 10.2. It should compile with most recent versions of Clang and GCC.

It also requires CMake 3.9:

cmake .
make
test/hull_unit_tests

Usage

About points

You can use your own definition of a point with the algorithms, if it contains (either):

• public x and y data members (or X and Y, upper case).
• public x and y methods (or X and Y, upper case).
• If your definition of a point provides different kinds of accessors to the coordinates, you can provide your specialization for the is_point template structure, and the x() and y() template functions.

Examples

The following code snippet demonstrates the way to use the iterator-based version of the algorithms:

#include "hull/algorithms.hpp"
#include <algorithm>
#include <iostream>
#include <vector>

struct point {
    double x, y;
};

int main() {
    std::vector<point> points{
        {5., 3.}, {8., 12.}, {3.14, 42.}
    };
    std::vector<point> convex_hull(points.size());
    
    const auto last = hull::compute_convex_hull(std::begin(points), std::end(points), std::begin(convex_hull));
    
    std::for_each(std::begin(convex_hull), last, [](const auto& p) {
        std::cout << "(" << p.x << ";" << p.y << ") ";
    });
    
    std::cout << std::endl;
}

The following code snippet shows the way to use the container-based version of the algorithms:

    std::vector<point> points{
        {5., 3.}, {8., 12.}, {3.14, 42.}
    };
    std::vector<point> convex_hull;
    
    hull::convex::compute(points, convex_hull);
    
    for (const auto& p: convex_hull) {
        std::cout << "(" << p.x << ";" << p.y << ") ";
    };
    
    std::cout << std::endl;

Library documentation

All the algorithms are defined in header algorithms.hpp, in the namespace hull.

Iterator-based algorithms

    template <typename RandomIt1, typename RandomIt2>
    RandomIt2 compute_convex_hull(Policy policy, RandomIt1 first, RandomIt1 last, RandomIt2 first2); // (1)
    
    template <typename Policy, typename RandomIt1, typename RandomIt2>
    RandomIt2 compute_convex_hull(RandomIt1 first, RandomIt1 last, RandomIt2 first2); // (2)
    
    template <typename RandomIt1, typename RandomIt2>
    RandomIt2 compute_convex_hull(RandomIt1 first, RandomIt1 last, RandomIt2 first2); // (3)

For all these algorithms:

• first is the random access iterator to the first point of the container.
• last is the random access iterator to the one-past last point of the container.
• first2 is the random access iterator to the first point of the destination container.
• it returns the iterator to the last element forming the convex hull of the destination container of points.
• The average time complexity is O(N * log(N)).

Specificities:

(1) The first parameter is a policy for the choice of the algorithm. It may be either hull::choice::graham_scan, hull::choice::monotone_chain, hull::choice::jarvis_march or hull::choice::chan.

(2) The policy is passed as a template parameter. It may be either hull::graham_scan_t, hull::monotone_chain_t, hull::jarvis_march_t or hull::chan_t.

(3) The default algorithm is Graham Scan.

Container-based algorithms

In the namespace hull::convex.

    template <typename TContainer1, typename TContainer2>
    void compute(Policy policy, const TContainer1& c1, TContainer2& c2); // (1)
    
    template <typename Policy, typename TContainer1, typename TContainer2>
    void compute(const TContainer1& c1, TContainer2& c2); // (2)
    
    template <typename TContainer1, typename TContainer2>
    void compute(const TContainer1& c1, TContainer2& c2); // (3)

For all these algorithms:

• c1 is the input container of points.
• c2 is the destination container that will contain the convex hull.

Specificities:

(1) The first parameter is a policy for the choice of the algorithm. It may be either hull::choice::graham_scan, hull::choice::monotone_chain, hull::choice::jarvis_march or hull::choice::chan.

(2) The policy is passed as a template parameter. It may be either hull::graham_scan_t, hull::monotone_chain_t, hull::jarvis_march_t or hull::chan_t.

(3) The default algorithm is Graham Scan.

Required enhancements

The following enhancements would be the next natural steps for this library:

• Implement Quickhull.
• Implement - or integrate an existing - tiny executor facility (thread pool + task queue).
• Implement a parallel version of Quickhull thanks to this executor.
• Perform a benchmark between the implementations of Graham Scan, Monotone Chain, Jarvis March and Chan's algorithm.
• Perform a benchmark with OpenCV and boost::geometry.
• Implement a GPGPU version of Quickhull with OpenCL.
• Use Bandit for unit testing instead of a home-made library.
• In C++20, everything should be rewritten with concepts, modules, ranges and reflection.