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
#include

namespace ConvexHull
{
template
struct Point
{
T x, y;

bool operator const &p) const
{
return x PointInt;
typedef Point PointDouble;
typedef std::vector PointIntArray;
typedef std::vector PointDoubleArray;

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

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

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

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

template
ConvexHull2d::ConvexHull2d() :
m_inPoints(),
m_hullPoints()
{
}

template
ConvexHull2d::ConvexHull2d(std::vector> const &in)
{
InitHull(in);
}

template
ConvexHull2d::~ConvexHull2d()
{
}

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

template
void ConvexHull2d::SetHullPoints(std::vector> const &in)
{
m_hullPoints.clear();
int n = static_cast(in.size()); //Total point count
if (n = 2 && cross(m_hullPoints[k - 2], m_hullPoints[k - 1], in[i]) = 0; i--)
{

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 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> 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> 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 
struct ConvexHull2d {
    ConvexHull2d() = default;

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

private:
    std::vector> m_inPoints;
    std::vector> 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::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 a

StackExchange Code Review Q#113986, answer score: 8