43 #ifdef CHECK_MEMORY_LEAKS
45 #endif // CHECK_MEMORY_LEAKS
57 int n = (
int) V.size();
58 std::vector<Position> D(2 * n + 1);
59 int bot = n - 2, top = bot + 3;
60 D[bot] = D[top] = V[2];
61 if (
isLeft(V[0], V[1], V[2]) > 0) {
70 for (
int i = 3; i < n; i++) {
72 if (bot >= (
int) D.size() || top - 1 >= (
int) D.size() || i >= (
int) V.size()) {
75 if ((
isLeft(D[bot], D[bot + 1], V[i]) > 0) &&
76 (
isLeft(D[top - 1], D[top], V[i]) > 0)) {
82 while (
isLeft(D[bot], D[bot + 1], V[i]) <= 0) {
84 if (bot >= (
int) D.size()) {
93 if (top == 0 || top >= (
int) D.size()) {
97 while (
isLeft(D[top - 1], D[top], V[i]) <= 0) {
99 if (top == 0 || top >= (
int) D.size()) {
104 if (top + 1 >= (
int) D.size()) {
113 for (h = 0; h <= (top - bot); h++) {
114 if (bot + h >= (
int) D.size()) {
SUMOReal isLeft(const Position &P0, const Position &P1, const Position &P2)
PositionVector simpleHull_2D(const PositionVector &V)
void push_back_noDoublePos(const Position &p)