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.
