The question asks to compute the convex hull of a set of 2D points. A convex hull is basically a series of consecutive line segments that suffice to enclose all the points in the area. In this exercise, I am using Jarvis's March algorithm.
Here is the code:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using uint = unsigned int;
struct Vector2D
{
int x_;
int y_;
Vector2D() : x_(0), y_(0) {}
Vector2D(int x, int y) : x_(x), y_(y) {}
Vector2D operator+(const Vector2D & vec) const
{
return Vector2D(x_ + vec.x_, y_ + vec.y_);
}
Vector2D operator-(const Vector2D & vec) const
{
return Vector2D(x_ - vec.x_, y_ - vec.y_);
}
};
using itVector2D = std::vector<Vector2D>::iterator;
enum RelativePosition { Clockwise, CounterClockwise };
RelativePosition ComparePosition(Vector2D target, Vector2D reference);
itVector2D findeNextVertex(std::vector<Vector2D> & coords, itVector2D itSource);
int main()
{
std::ifstream file;
file.open("data.txt");
if (!file.is_open())
{
std::cerr << "unable to open file" << std::endl;
return -1;
}
// total number of points
uint nPoints = 0;
file >> nPoints;
// creating data set
std::vector<Vector2D> coords;
coords.reserve(nPoints);
// reading data set
Vector2D temp;
for (uint i = 0; i < nPoints; ++i)
{
file >> temp.x_ >> temp.y_;
coords.push_back(temp);
}
// find the topmost
itVector2D itTopMost = std::max_element(coords.begin(), coords.end(),
[](const Vector2D & a, const Vector2D & b) { return a.y_ < b.y_; });
// while it doesnt trace back to origin
// perform algorithm once to get to the next vertex
itVector2D itCurrent = itTopMost;
do
{
itCurrent = findeNextVertex(coords, itCurrent);
std::cout << itCurrent->x_ << " " << itCurrent->y_ << std::endl;
} while (itCurrent != itTopMost);
return 0;
}
RelativePosition ComparePosition(Vector2D target, Vector2D reference)
{
// compute determinant to determine if it is CW or CCW
return reference.y_ * target.x_ - reference.x_ * target.y_ > 0 ? Clockwise : CounterClockwise;
}
// find next convex hull vertex
itVector2D findeNextVertex(std::vector<Vector2D> & coords, itVector2D itSource)
{
for (itVector2D itTarget = coords.begin(); itTarget != coords.end(); ++itTarget)
{
// if itTarget is the same point as itSource, skip this case
if (itTarget == itSource)
{
continue;
}
// assume itTarget is counterclockwise to all itReference
bool allCC = true;
// for other cases, find out if itTarget is counter-clockwise to all the itReference
for (itVector2D itReference = coords.begin(); itReference != coords.end(); ++itReference)
{
if (itReference == itTarget || itReference == itSource)
{
continue;
}
Vector2D vecTarget = *itTarget - *itSource;
Vector2D vecReference = *itReference - *itSource;
if (ComparePosition(vecTarget, vecReference) != CounterClockwise)
{
allCC = false;
break;
}
}
// if this itTarget is counter-clockwise to all the itReference
if (allCC)
{
return itTarget;
}
}
}
I have tested one set of data below (named as "data.txt
" in the code), which is correct.
12
5 19
33 2
-5 88
54 5
12 13
18 39
15 42
17 -5
-3 23
9 29
-8 17
-1 25
I am quite new to C++, so any feedback is appreciated. Here are some questions that I have after writing this code:
I encountered many cases where data type is unsigned int, especially for the case,
for(unsigned int i = ...; i < ....; ++i)
So I useusing uint = unsigned int
. Is it necessary to do so? Especially for the "for() loop" case, because it bothers me quite often.I only check if file can be correctly read at the very beginning, but have no idea about how to safely read the following content. A general guidance covering this would be appreciated.
I created a temp
Vector2D
object to store a pair of coordinate temporarily and push it into the vector afterwards. Can I avoid creating this temp object?When finding the topmost vertex, I used
std::max_element
. However I found that it doesn't really depend on this function but the lambda function I wrote after. If I flip the comparative "return a.y_ < b.y_;
" to greater than, it gives me different answer. So what doesstd::max_element
really do?I have seen people say underscore after or before variable name is reserved. However, others don't really think it causes trouble in scope. Is it okay to use it as I did in the code for
Vector2D
? A recommended way is to usem_variableName
, but I don't really like this format.
Any other feedback or comments are also welcome!
using
is much better than preprocessor#define
, as it respects context correctly.#define
is pure text substitution, and I don't recommend it where there's any alternative. \$\endgroup\$typedef
. Thanks for commenting @TobySpeight! \$\endgroup\$