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.
Template class for Andrew's Monotone Chain Algorithm Convex Hull
c++;computational geometry
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 ConvexHullIt'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 withnamespace ConvexHull {namespace detail {...} // namespace detail} // namespace ConvexHullor, as some would write it,namespace ConvexHull { namespace detail {...} // namespace ConvexHull::detailC++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 constructorConvexHull2d(std::vector<Point<T>> const &in);(which by the way should be explicit). So if I'm ever tempted to writeConvexHull2d empty;empty.InitHull(somevector);what I really should write isConvexHull2d empty(somevector);And if I'm tempted to writeConvexHull2d empty;if (somecondition) {    empty.InitHull(somevector);} else {    empty.InitHull(someothervector);}then what I should write isConvexHull2d 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_inPointsto remove the member m_inPoints altogether, since it's never exposed to the userto 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. :)