/*
* Convex hull algorithm - Library (C++)
*
* Copyright (c) 2021 Project Nayuki
* https://www.nayuki.io/page/convex-hull-algorithm
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this program (see COPYING.txt and COPYING.LESSER.txt).
* If not, see .
*/
#include
#include "ConvexHull.hpp"
using std::vector;
bool Point::operator==(const Point &other) const {
return x == other.x && y == other.y;
}
bool Point::operator!=(const Point &other) const {
return x != other.x || y != other.y;
}
bool Point::operator<(const Point &other) const {
if (x != other.x) return x < other.x;
else return y < other.y;
}
bool Point::operator>(const Point &other) const {
if (x != other.x) return x > other.x;
else return y > other.y;
}
bool Point::operator<=(const Point &other) const {
if (x != other.x) return x < other.x;
else return y <= other.y;
}
bool Point::operator>=(const Point &other) const {
if (x != other.x) return x > other.x;
else return y >= other.y;
}
vector makeConvexHull(vector points) {
std::sort(points.begin(), points.end());
return makeConvexHullPresorted(points);
}
vector makeConvexHullPresorted(const vector &points) {
if (points.size() <= 1)
return vector(points);
// Andrew's monotone chain algorithm. Positive y coordinates correspond to "up"
// as per the mathematical convention, instead of "down" as per the computer
// graphics convention. This doesn't affect the correctness of the result.
vector upperHull;
for (const Point &p : points) {
while (upperHull.size() >= 2) {
const Point &q = *(upperHull.cend() - 1); // Same as .back()
const Point &r = *(upperHull.cend() - 2);
if ((q.x - r.x) * (p.y - r.y) >= (q.y - r.y) * (p.x - r.x))
upperHull.pop_back();
else
break;
}
upperHull.push_back(p);
}
upperHull.pop_back();
vector lowerHull;
for (vector::const_reverse_iterator it = points.crbegin(); it != points.crend(); ++it) {
const Point &p = *it;
while (lowerHull.size() >= 2) {
const Point &q = *(lowerHull.cend() - 1); // Same as .back()
const Point &r = *(lowerHull.cend() - 2);
if ((q.x - r.x) * (p.y - r.y) >= (q.y - r.y) * (p.x - r.x))
lowerHull.pop_back();
else
break;
}
lowerHull.push_back(p);
}
lowerHull.pop_back();
if (!(upperHull.size() == 1 && upperHull == lowerHull))
upperHull.insert(upperHull.end(), lowerHull.cbegin(), lowerHull.cend());
return upperHull;
}