Quick Hull Algorithm implementation for higher dimensions

Last version of library (performance has been improved drastically since posting).

I tried to implement the Quick Hull Algorithm for computing the convex hull of a finite set of D-dimensional points. Algorithm itself:

```
#pragma once

#include
#include
#include

#include
#include
#include
#include
#include
#include
#include
#include
#include

#include

struct bad_geometry
: std::exception
{

virtual
~bad_geometry() noexcept = default;

bad_geometry() = default;

explicit
bad_geometry(const char * const _what)
: what_(_what)
{ ; }

explicit
bad_geometry(std::string const & _what)
: what_(_what)
{ ; }

virtual
const char *
what() const noexcept override
{
return what_.c_str();
}

private :

std::string const what_ = "bad_geometry";

};

using boolean_type = bool;
using size_type = std::size_t;

template
F
determinant(boost::numeric::ublas::matrix _m)
{
size_type const size_ = _m.size1();
assert(_m.size2() == size_);
boost::numeric::ublas::permutation_matrix pm_(size_);
if (0
struct convex_hull
{

using G = typename point_type::value_type;
using point_refs_type = std::deque >;
using point_list = std::list;
using point_set = std::set;
using points_type = std::deque;

template
convex_hull(ForwardIterator _first, ForwardIterator _last)
: dimension_(_first->size())
, points_(_first, _last)
{
assert(0 ;

struct facet // (d - 1)-dimensional faces
{

template
facet(ForwardIterator first, ForwardIterator mid, ForwardIterator last,
boolean_type const _outward)
: vertices_(first, std::prev(mid))
, points_(vertices_.cbegin(), vertices_.cend())
, outward_(_outward)
{
auto const rest = vertices_.insert(vertices_.cend(), mid, last);
points_.insert(points_.cend(), rest, vertices_.end());
st

None of this exception is needed:

struct bad_geometry
        : std::exception
{

    virtual
    ~bad_geometry() noexcept = default;

    bad_geometry() = default;

    explicit
    bad_geometry(const char * const _what)
        : what_(_what)
    { ; }

    explicit
    bad_geometry(std::string const & _what)
        : what_(_what)
    { ; }

    virtual
    const char *
    what() const noexcept override
    {
        return what_.c_str();
    }

private :

    std::string const what_ = "bad_geometry";

};

Replace with:

struct bad_geometry
        : std::runtime_error
{
    explicit
    bad_geometry(char const* what)
        : std::rutime_error(what)
    {}

    explicit
    bad_geometry(std::string const& what)
        : std::runtime_error(what.c_str())
    {}
};

Pass by value:

template
F determinant(boost::numeric::ublas::matrix _m)

Here _m is being passed by value. Thus it is probably generating a copy of the matrix. Passs by const reference to avoid the copy.

template
F determinant(boost::numeric::ublas::matrix const& m)

Lets stick all the using clauses together:

using points_type = std::deque;

/// LOTS OF STUFF

struct facet;

using facet_set = std::set;  // Stick this with the others.

If your code is inlined (like this); Then its easier to read a class if you put the variables first. Then I can read the constructors with a context of what values need to be set in what order:

// These defined way after the constructors use them.

    points_type vertices_; // oriented
    points_type points_;   // non-oriented
    boolean_type outward_;
    facet_set neighbours_;
    points_type outside_set_; // if not empty, then first point is furthest for this facet

This one is a take it or leave it (not a big deal).

// This is fine.
        if (outward_) {
            return (_nearer < _further);
        } else {
            return (_further < _nearer);
        }

   // But I would write it like this:

        return (outward_)
             ? (_nearer < _further)
             : (_further < _nearer);

Your code is very dense (and thus hard to read). A bit more white space is not going to kill you and some explanation. Its hard to tell if there is any more unnecessary copying because of your use of auto (I hope you only use it for things where the type does not matter (iterators and the like)).

StackExchange Code Review Q#54178, answer score: 3