75 lines
1.9 KiB
C++
75 lines
1.9 KiB
C++
/*
|
||
* © Copyright 2014 – Urheberrechtshinweis
|
||
* Alle Rechte vorbehalten / All Rights Reserved
|
||
*
|
||
* Programmcode ist urheberrechtlich geschuetzt.
|
||
* Das Urheberrecht liegt, soweit nicht ausdruecklich anders gekennzeichnet, bei Frank Ebner.
|
||
* Keine Verwendung ohne explizite Genehmigung.
|
||
* (vgl. § 106 ff UrhG / § 97 UrhG)
|
||
*/
|
||
|
||
#ifndef GEO_CONVEXHULL2_H
|
||
#define GEO_CONVEXHULL2_H
|
||
|
||
#include "Point2.h"
|
||
|
||
#include <algorithm>
|
||
#include <vector>
|
||
|
||
/**
|
||
* get a convex-hull around a set of 2D points
|
||
* https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
|
||
*/
|
||
class ConvexHull2 {
|
||
|
||
public:
|
||
|
||
//using namespace std;
|
||
|
||
typedef double coord_t; // coordinate type
|
||
typedef double coord2_t; // must be big enough to hold 2*max(|coordinate|)^2
|
||
|
||
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
|
||
// Returns a positive value, if OAB makes a counter-clockwise turn,
|
||
// negative for clockwise turn, and zero if the points are collinear.
|
||
static inline coord2_t cross(const Point2 O, const Point2 A, const Point2 B) {
|
||
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
|
||
}
|
||
|
||
// Returns a list of points on the convex hull in counter-clockwise order.
|
||
// Note: the last point in the returned list is the same as the first one.
|
||
static inline std::vector<Point2> get(std::vector<Point2> P) {
|
||
|
||
auto comp = [] (const Point2 p1, const Point2 p2) {
|
||
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
|
||
};
|
||
|
||
int n = P.size(), k = 0;
|
||
if (n == 1) return P;
|
||
std::vector<Point2> H(2*n);
|
||
|
||
// Sort points lexicographically
|
||
std::sort(P.begin(), P.end(), comp);
|
||
|
||
// Build lower hull
|
||
for (int i = 0; i < n; ++i) {
|
||
while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
|
||
H[k++] = P[i];
|
||
}
|
||
|
||
// Build upper hull
|
||
for (int i = n-2, t = k+1; i >= 0; i--) {
|
||
while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
|
||
H[k++] = P[i];
|
||
}
|
||
|
||
H.resize(k-1);
|
||
return H;
|
||
|
||
}
|
||
|
||
|
||
};
|
||
|
||
#endif // GEO_CONVEXHULL2_H
|