53 int n = (int) V.size();
54 std::vector<Position> D(2 * n + 1);
55 int bot = n - 2, top = bot + 3;
56 D[bot] = D[top] = V[2];
57 if (
isLeft(V[0], V[1], V[2]) > 0) {
66 for (
int i = 3; i < n; i++) {
68 if (bot >= (
int) D.size() || top - 1 >= (int) D.size() || i >= (int) V.size()) {
71 if ((
isLeft(D[bot], D[bot + 1], V[i]) > 0) &&
72 (
isLeft(D[top - 1], D[top], V[i]) > 0)) {
78 while (
isLeft(D[bot], D[bot + 1], V[i]) <= 0) {
80 if (bot >= (
int) D.size()) {
89 if (top == 0 || top >= (
int) D.size()) {
93 while (
isLeft(D[top - 1], D[top], V[i]) <= 0) {
95 if (top == 0 || top >= (
int) D.size()) {
100 if (top + 1 >= (
int) D.size()) {
109 for (h = 0; h <= (top - bot); h++) {
110 if (bot + h >= (
int) D.size()) {
PositionVector simpleHull_2D(const PositionVector &V)
void push_back_noDoublePos(const Position &p)
insert in back a non double position
double isLeft(const Position &P0, const Position &P1, const Position &P2)