I have done the algorithm the expected output is :
p00 - p01,
p01 - p03 ,
p03 - p10,
p10 - p12 ,
p12 - p00
But I get this instead:
Convex hull:
p00 - p01
p01 - p03
p03 - p05
p05 - p10
p10 - p00
Points:
p00: (-5,-6)
p01: (6,-4)
p02: (5.5,-3)
p03: (8,0)
p04: (5,0)
p05: (4,2)
p06: (1,3)
p07: (0,2)
p08: (-1,1)
p09: (-1.5,2)
p10: (-1.5,6)
p11: (-5.5,1.5)
p12: (-8,-1)
I have been trying so long to get it right but some how I can't. Can anyone help? I am using C++
Below is my code:
I have 3 classes Vector2D, Point2D and Point2DSet my Graham Scan Implementation is in the buildConvexHull function in the Point2DSet.
Vector2D.cpp
#include "Vector2D.h"
Vector2D::Vector2D(double aX, double aY): fX(aX), fY(aY){ }
void Vector2D::setX(double aX){ fX = aX;}
double Vector2D::getX() const { return fX; }
void Vector2D::setY(double aY) { fY = aY;}
double Vector2D::getY() const { return fY; }
Vector2D Vector2D::operator+(const Vector2D& aRHS) const
{
return (fX + aRHS.fX, fY + aRHS.fY);
}
Vector2D Vector2D::operator-(const Vector2D& aRHS) const
{
return (fX - aRHS.fX, fY - aRHS.fY);
}
double Vector2D::magnitude() const
{
return sqrt((fX * fX) + (fY * fY));
}
double Vector2D::direction() const
{
return atan(fY/fX);
}
double Vector2D::dot(const Vector2D& aRHS) const
{
return (this->getX() * aRHS.getX()) + (this->getY() * aRHS.getY());
}
double Vector2D::cross(const Vector2D& aRHS) const
{
return (this->getX() * aRHS.getY()) - (aRHS.getX() * this->getY());
}
double Vector2D::angleBetween(const Vector2D& aRHS) const
{
double dntmr = magnitude() * aRHS.magnitude();
if (dntmr > 0.0)
{
return acos(this->dot(aRHS) / (this->magnitude() * aRHS.magnitude()));
}
return acos(1.0/1.0);
}
std::ostream& operator<<(std::ostream& aOutStream, const Vector2D& aObject)
{
aOutStream << " ( " << aObject.fX << ", " << aObject.fY << " )\n";
return aOutStream;
}
std::istream& operator>>(std::istream& aInStream, Vector2D& aObject)
{
aInStream >> aObject.fX;
aInStream >> aObject.fY;
return aInStream;
}
Point2D
#include "Point2D.h"
static const Point2D gCoordinateOrigin;
// Private function gets direction in reference to aOther
double Point2D::directionTo(const Point2D& aOther) const
{
return (aOther.fPosition - fPosition).direction();
}
// Private Function to get magnitude in reference to aOther
double Point2D::magnitudeTo(const Point2D& aOther) const
{
return (aOther.fPosition - fPosition).magnitude();
}
Point2D::Point2D() : fId(" "), fPosition(0,0), fOrigin(&gCoordinateOrigin) { }
Point2D::Point2D(const std::string& aId, double aX, double aY) : fId(aId), fPosition(aX,aY), fOrigin(&gCoordinateOrigin) { }
Point2D::Point2D(std::istream &aIStream) : fOrigin(&gCoordinateOrigin)
{
aIStream >> fId >> fPosition;
}
const std::string& Point2D::getId() const { return fId; }
void Point2D::setX(const double& aX) { fPosition.setX(aX); }
void Point2D::setY(const double& aY) { fPosition.setY(aY); }
const double Point2D::getX() const { return fPosition.getX(); }
const double Point2D::getY() const { return fPosition.getY(); }
void Point2D::setOrigin(const Point2D& aPoint) { fOrigin = &aPoint;}
Vector2D Point2D::operator-(const Point2D& aRHS) const
{
return (fPosition - aRHS.fPosition);
}
// Return Direction with reference to origin
double Point2D::direction() const
{
return fOrigin->directionTo(*this);
}
// Return Direction with reference to origin
double Point2D::magnitude() const
{
return fOrigin->magnitudeTo(*this);;
}
bool Point2D::isCollinear(const Point2D& aOther) const
{
if (fPosition.cross(aOther.fPosition) == 0)
{
return true;
}
return false;
}
// Check to see if the point is Clockwise or not
bool Point2D::isClockwise(const Point2D& aP0, const Point2D& aP2) const
{
double val = (fPosition.getY() - aP0.fPosition.getY()) * (aP2.fPosition.getX() - fPosition.getX()) -
(fPosition.getX() - aP0.fPosition.getX()) * (aP2.fPosition.getY() - fPosition.getY());
double val2 = fPosition.angleBetween(aP2.fPosition) - fPosition.angleBetween(aP0.fPosition);
if (val < 0 )
{
return false;
}
return true;
}
bool Point2D::operator<(const Point2D& aRHS) const
{
if (fPosition.getY() < aRHS.getY())
{
return true;
}
return false;
}
const Point2D& Point2D::getOrigin() const { return *fOrigin;}
std::ostream& operator<<(std::ostream& aOStream, const Point2D& aObject)
{
aOStream << aObject.fId << " : " << aObject.fPosition;
return aOStream;
}
std::istream& operator>>(std::istream& aIStream, Point2D& aObject)
{
aIStream >> aObject.fId >> aObject.fPosition;
return aIStream;
}
Point2DSet
#include "Point2DSet.h"
#include <fstream>
#include <stdexcept>
#include <algorithm>
void Point2DSet::add(const Point2D& aPoint)
{
fPoints.push_back(aPoint);
}
void Point2DSet::add(Point2D&& aPoint)
{
fPoints.push_back(aPoint);
}
void Point2DSet::removeLast()
{
fPoints.pop_back();
}
bool Point2DSet::doesNotTurnLeft(const Point2D& aPoint) const
{
return fPoints[size()-1].isClockwise(fPoints[size()-2],aPoint);
}
// Comparator function for Stable_sort
bool orderByCoordinates(const Point2D& aLeft, const Point2D& aRight)
{
return aLeft < aRight;
}
//Comparator function for Stable_sort
bool orderByPolarAngle(const Point2D& aLHS, const Point2D& aRHS)
{
if (aLHS.isCollinear(aRHS))
{
return aLHS.magnitude() > aRHS.magnitude();
}
return aLHS.direction() < aRHS.direction();
}
void Point2DSet::populate(const std::string& aFileName)
{
std::ifstream INPUT(aFileName);
//std::ifstream INPUT("Pointers.txt");
std::string id;
double x;
double y;
while (INPUT >> id >> x >> y)
{
Point2D z(id, x, y);
add(z);
}
INPUT.close();
}
void Point2DSet::buildConvexHull(Point2DSet& aConvexHull)
{
aConvexHull.clear();
sort(orderByCoordinates);
sort(orderByPolarAngle);
aConvexHull.add(fPoints[0]); // Origin (Smallest y-coordinate)
aConvexHull.add(fPoints[1]); //
//aConvexHull.add(fPoints[2]);
if (fPoints[2].isCollinear(fPoints[1])) {
aConvexHull.add(fPoints[2]);
}
//*/
for(size_t i = 3; i < size(); i++)
{
if (fPoints[i - 1].isCollinear(fPoints[i]))
{
continue; //i++;
}
if(aConvexHull.doesNotTurnLeft(fPoints[i]))
{
aConvexHull.removeLast();
}
aConvexHull.add(fPoints[i]);
}//*/
}
size_t Point2DSet::size() const
{
return fPoints.size();
}
void Point2DSet::clear()
{
fPoints.clear();
}
void Point2DSet::sort(Comparator aComparator)
{
stable_sort(fPoints.begin(), fPoints.end(), aComparator);
}
const Point2D& Point2DSet::operator[](size_t aIndex) const
{
return fPoints[aIndex];
}
Point2DSet::Iterator Point2DSet::begin() const
{
return fPoints.begin();
}
Point2DSet::Iterator Point2DSet::end() const
{
return fPoints.end();
}
Any other improvements are warmly welcome. Thank You!
There was a few issues in your code.
Let's start with Vector2D::direction(), you should use atan2, here the explanation why. After that we will be able to correctly sort the points.
Now the main algorithm. After a few changes it looks:
aConvexHull.clear();
// Get points with bigger magnitude first.
sort(orderByMagnitudeDescending);
sort(orderByPolarAngle);
// We want to have the lowest point as the first element.
rotatePointsByLowest();
aConvexHull.add(fPoints[0]); // Origin (Smallest y-coordinate)
aConvexHull.add(fPoints[1]);
for(size_t i = 2; i < size(); i++)
{
if (fPoints[i - 1].isCollinear(fPoints[i]))
{
continue; //i++;
}
// There should be a loop instead of an if statement.
while (aConvexHull.fPoints.size() > 2 && aConvexHull.doesNotTurnLeft(fPoints[i]))
{
aConvexHull.removeLast();
}
aConvexHull.add(fPoints[i]);
}//*/
The algorithm requires to find the lowest point and then traverse the rest of points according to their angle. I added a helper function Point2DSet::rotatePointsByLowest:
void Point2DSet::rotatePointsByLowest() {
auto lowestPoint = fPoints.begin();
for (auto iterator = fPoints.begin() + 1;iterator != fPoints.end(); iterator++) {
if (iterator->fPosition.fY < lowestPoint->fPosition.fY) {
lowestPoint = iterator;
} else if ((iterator->fPosition.fY == lowestPoint->fPosition.fY) && (iterator->fPosition.fX < lowestPoint->fPosition.fX)) {
lowestPoint = iterator;
}
}
std::rotate(fPoints.begin(), lowestPoint, fPoints.end());
}
There are more improvements that should be applied but I wanted to keep the changes minimal to show the issues causing the incorrect result.
Link for testing your project: https://onlinegdb.com/_ZXmQF2vJ