# Template class for Andrew's Monotone Chain Algorithm Convex Hull

This is my first attempt at writing a template class. I am implementing Andrew's Monotone Chain algorithm, as described here to calculate a 2D Convex Hull. Since this is my first try at templates, I would like a review of my code to make sure I get started on the right track.

ConvexHull2d.h

// ConvexHull2D
// Template class to calculate a 2D convex hull from a set of 2d points
// Uses Andrew's Monotone Chain Algorithm
// Algorithm based on code found at this web site:
// https://en.m.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
//
#pragma once

#include <vector>
#include <algorithm>

namespace ConvexHull
{
template <typename T>
struct Point
{
T x, y;

bool operator <(Point<T> const &p) const
{
return x < p.x || (x == p.x && y < p.y);
}

Point() :
x(0),
y(0)
{
}

Point(T const tx, T const ty) :
x(tx),
y(ty)
{
}
};

typedef Point<int> PointInt;
typedef Point<double> PointDouble;
typedef std::vector<PointInt> PointIntArray;
typedef std::vector<PointDouble> PointDoubleArray;

template <typename T>
T cross(Point<T> const &o, Point<T> const &a, Point<T> const &b)
{
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

template <typename T>
class ConvexHull2d
{
public:
ConvexHull2d();
ConvexHull2d(std::vector<Point<T>> const &in);
~ConvexHull2d();

void InitHull(std::vector<Point<T>> const &in);
std::vector<Point<T>> GetHullPoints() const;

private:
std::vector<Point<T>> m_inPoints;
std::vector<Point<T>> m_hullPoints;
void SetHullPoints(std::vector<Point<T>> const &in);
};

template <typename T>
ConvexHull2d<T>::ConvexHull2d() :
m_inPoints(),
m_hullPoints()
{
}

template <typename T>
ConvexHull2d<T>::ConvexHull2d(std::vector<Point<T>> const &in)
{
InitHull(in);
}

template <typename T>
ConvexHull2d<T>::~ConvexHull2d()
{
}

template <typename T>
void ConvexHull2d<T>::InitHull(std::vector<Point<T>> const &in)
{
m_inPoints = in;
sort(m_inPoints.begin(), m_inPoints.end());
SetHullPoints(m_inPoints);
}

template <typename T>
void ConvexHull2d<T>::SetHullPoints(std::vector<Point<T>> const &in)
{
m_hullPoints.clear();
int n = static_cast<int>(in.size()); //Total point count
if (n < 3)
return;
int k = 0;
m_hullPoints.resize(2 * n);
// Build lower hull
for (int i = 0; i < n; i++)
{
while (k >= 2 && cross(m_hullPoints[k - 2], m_hullPoints[k - 1], in[i]) <= 0)
k--;
m_hullPoints[k++] = in[i];
}
// Build upper hull
for (int i = n - 2, t = k + 1; i >= 0; i--)
{
while (k >= t && cross(m_hullPoints[k - 2], m_hullPoints[k - 1], in[i]) <= 0)
k--;
m_hullPoints[k++] = in[i];
}
m_hullPoints.resize(k-1); // This removes the last point added since it is the same as first point
}

template <typename T>
std::vector<Point<T>> ConvexHull2d<T>::GetHullPoints() const
{
return m_hullPoints;
}
}


Here is a program to test the class. It generates random integer and double points then calculates the convex hull.

main.cpp

#include "ConvexHull2d.h"
#include <iostream>
#include <vector>
#include <random>
#include <ctime>

double randomNumber(double mn, double mx);
int randomNumber(int mn, int mx);

using namespace ConvexHull;

int main()
{
size_t const count = 100;
int const minInt = -10;
int const maxInt = 10;
double const minDouble = -10.0;
double const maxDouble = 10.0;

std::srand(static_cast<unsigned int>(std::time(0)));
PointIntArray intPoints;
for (size_t i = 0; i < count; ++i)
{
int dx = randomNumber(minInt, maxInt);
int dy = randomNumber(minInt, maxInt);
intPoints.push_back(PointInt(dx, dy));
}
ConvexHull2d<int> intHull(intPoints);
PointIntArray intHullPoints = intHull.GetHullPoints();

PointDoubleArray doublePoints;
for (size_t i = 0; i < count; ++i)
{
double dx = randomNumber(minDouble, maxDouble);
double dy = randomNumber(minDouble, maxDouble);
doublePoints.push_back(PointDouble(dx, dy));
}

ConvexHull2d<double> doubleHull;
doubleHull.InitHull(doublePoints);
PointDoubleArray doubleHullPoints = doubleHull.GetHullPoints();

std::cout << "Random doubles\n";
for (size_t i = 0; i < doublePoints.size(); ++i)
std::cout << doublePoints[i].x << ", " << doublePoints[i].y << std::endl;

std::cout << "\nDouble Convex Hull points\n";
for (size_t i = 0; i < doubleHullPoints.size(); ++i)
std::cout << doubleHullPoints[i].x << ", " << doubleHullPoints[i].y << std::endl;

std::cout << "\nRandom integers\n";
for (size_t i = 0; i < intPoints.size(); ++i)
std::cout << intPoints[i].x << ", " << intPoints[i].y << std::endl;

std::cout << "\nInteger Convex Hull points\n";
for (size_t i = 0; i < intHullPoints.size(); ++i)
std::cout << intHullPoints[i].x << ", " << intHullPoints[i].y << std::endl;

return 0;
}

double randomNumber(double mn, double mx)
{
return mn + (static_cast<double>(std::rand()) / RAND_MAX) * (mx - mn);
}

int randomNumber(int mn, int mx)
{
return mn + (static_cast<int>(std::rand()) % (mx - mn));
}


I am mainly interested in a review of my class, but any comments on the test program are welcome, as well.

SPOILER ALERT: you don't want a class at all; you want a function.

But first, the style nitpicks! :)

namespace ConvexHull
{
void foo();
...
}


You'll find that a significant fraction of C++ programmers today "collapse" their namespaces like this:

namespace ConvexHull {

void foo();
...

} // namespace ConvexHull


It's a little bit "weird" to have an opening curly brace without indenting the following lines; but it's equally "weird" to have a (non-member) function definition that doesn't begin in column 1, and having to indent all your code past column 1 is much more painful to read and write. The benefits of "collapsed" style really start to show themselves with

namespace ConvexHull {
namespace detail {

...

} // namespace detail
} // namespace ConvexHull


or, as some would write it,

namespace ConvexHull { namespace detail {

...

} // namespace ConvexHull::detail


C++17 will probably support opening a multi-level namespace with namespace ConvexHull::detail { } directly.

Another "inconsistent" style preference that you'll see modern C++ programmers have moved toward is the placement of ampersands: const Foo& x instead of const Foo &x. The former is just easier to read, especially when you've got things like T&& t (versus T &&t). And yes, C++ programmers tend to agree with C programmers that it's correct to write const int *p, not const int* p. "Weird", yes, but it's all about readability.

It's strange that you spell the name of the class ConvexHull2d, but you don't spell the name of the helper class Point2d (it's just "Point"). What would you do if I wanted a ConvexHull3d?

You define typedefs for PointInt, PointDouble, PointIntArray, and PointDoubleArray, but then never use them. This is terribly bad style and you should get out of this habit.

• Why would the user ever want to use PointInt, when Point<int> is only two characters longer, and makes it much more clear what's going on?

• PointIntArray is not an array (neither a C-style array nor a std::array), so that's not even a good name for it.

void InitHull(std::vector<Point<T>> const &in);


What's up with this member function? It seems like this method is provided only so that you can shove a new set of points into an existing ConvexHull2d object. But it doesn't really make sense to have a ConvexHull2d without a point-set; in fact you already provide a constructor

ConvexHull2d(std::vector<Point<T>> const &in);


(which by the way should be explicit). So if I'm ever tempted to write

ConvexHull2d empty;
empty.InitHull(somevector);


what I really should write is

ConvexHull2d empty(somevector);


And if I'm tempted to write

ConvexHull2d empty;
if (somecondition) {
empty.InitHull(somevector);
} else {
empty.InitHull(someothervector);
}


then what I should write is

ConvexHull2d empty;
if (somecondition) {
empty = ConvexHull2d(somevector);
} else {
empty = ConvexHull2d(someothervector);
}


There's no reason for the InitHull named method to exist. Use constructors and assignment operators for their designed purpose.

Relying on ADL to find std::sort is the bad kind of weird, and I'd say you shouldn't do it.

Your internal helpers InitHull and SetHullPoints aren't sufficiently differentiated to warrant two different entry points. Fortunately, we've just shown that InitHull is completely unnecessary. I'd argue that SetHullPoints is also unnecessary and should be inlined right into the constructor. That is:

template <typename T>
struct ConvexHull2d {
ConvexHull2d() = default;

explicit ConvexHull2d(const std::vector<Point<T>>& in)
: m_inPoints(in)
{
std::sort(m_inPoints.begin(), m_inPoints.end());
int n = in.size();
if (n < 3) return;
int k = 0;
m_hullPoints.resize(2 * n);
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(m_hullPoints[k - 2], m_hullPoints[k - 1], in[i]) <= 0) {
k--;
}
m_hullPoints[k++] = in[i];
}
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && cross(m_hullPoints[k - 2], m_hullPoints[k - 1], in[i]) <= 0) {
k--;
}
m_hullPoints[k++] = in[i];
}
m_hullPoints.resize(k-1);
}

std::vector<Point<T>> GetHullPoints() const {
return m_hullPoints;
}

private:
std::vector<Point<T>> m_inPoints;
std::vector<Point<T>> m_hullPoints;
};


Notice that I'm adhering to the Rule of Zero: the compiler-generated destructor is good enough for me, so I don't need to write it out explicitly. Similarly, I don't need to write out the body of the default constructor; I can just =default it. And I don't need to write a member-initializer for m_hullPoints; I can rely on the compiler to default-initialize that vector to the empty state.

I do, however, provide a default constructor, because without a default constructor you can't do some really useful things such as call std::vector<ConvexHull2d>::resize().

Depending on how this class is going to be used in practice, you might prefer:

• to take in by value instead of by const-reference, and move it into m_inPoints
• to remove the member m_inPoints altogether, since it's never exposed to the user
• to have GetHullPoints() return a const-reference to m_hullPoints, instead of always returning a copy of m_hullPoints (for example if the caller just wants to iterate over it, not store or modify it)

It's a little strange to write cross(o, a, b) instead of cross(a - o, b - o) with a suitably overloaded operator-(Point, Point). However, I could totally believe that cross(o, a, b) turns out to be faster for some reason, so maybe that strangeness is on purpose.

Are you planning to add any more members to the ConvexHull2d class? Because if not, I would strongly consider getting rid of the class altogether! Don't you just want a plain old function?

template<class Pt>
std::vector<Pt> GetHullPoints(std::vector<Pt> in)
{
auto lex_less = [](const Pt& a, const Pt& b) { return std::tie(a.x, a.y) < std::tie(b.x, b.y); };
std::sort(in.begin(), in.end(), lex_less);
...
return hullPoints;
}


Not every abstraction in C++ requires a class — in fact, precious few do. If all you're doing here is transforming one pointset into a slightly sparser pointset, then that sounds like an excellent job for a function.

Also notice that by getting rid of the need to store the data long-term, I've been able to generalize my algorithm. Now instead of taking Point<T> for any T, it can actually operate on any type Pt at all, as long as a variable of type Pt has a member .x and a member .y. This means that in my header that defines the GetHullPoints function, I don't need to define class Point at all; it's no longer part of my interface. Let the user worry about choosing the best representation for 2D points; all I care about is my algorithm for computing convex hulls!

For more about generalizing algorithms and separating the algorithm from the representation of the data type, I weakly recommend Alexander Stepanov's lectures. They're a bit long and digression-laden, but there's some good stuff in there.

So we started with "let's remove 2 spaces of indentation from every line in the file", passed through "let's remove two helper methods by inlining them", and finished up with "let's remove the entire class, along with all of Point"! This is a common pattern in modern C++ programming — and actually in all programming. Eliminate all inessential complexity, and you'll find that what is left is the essence of the problem you're trying to solve. :)

• Thank you for this review. I will study all the points you make and may have a few more questions. I do want to add methods to the class for object oriented bounding box, centroid and area. Should I still just use functions? – Paul H. Dec 15 '15 at 13:37
• I learned a lot from this review. Your points are all well taken. However, there is one line of code you proposed that is still "magic" to me: auto lex_less = [](const Pt& a, const Pt& b) { return std::tie(a.x, a.y) < std::tie(b.x, b.y); }; I understand that it is defining a comparison function for std::sort, but I am having trouble understanding what exactly is going on. My best guess is it compares the first arguments, and returns result if not equal. If first parameters are equal, it then compares the second parameters. Is this correct? – Paul H. Dec 16 '15 at 17:59
• If you're going to add more methods to the class that would benefit from sharing some of the data, then yes, a class is probably a good idea. At which point the interesting question becomes "how to keep from paying for the computation of bounding box, centroid, etc, if the user will never actually ask for them?" vs "how to avoid paying twice if the user asks twice?". As for the semantics of std::tie, first look up what std::tie does (it returns a std::tuple) and then look up the semantics of operator< on tuples. en.cppreference.com/w/cpp/utility/tuple/operator_cmp – Quuxplusone Dec 19 '15 at 1:37
• Concerning the paying for the computations, what do you think about calculating when the get method is called then setting a bool variable? The get method would check the status of the variable before the calculations and respond accordingly. – Paul H. Dec 19 '15 at 16:45