SUMO - Simulation of Urban MObility
Helper_ConvexHull.cpp
Go to the documentation of this file.
1 /****************************************************************************/
8 // Copyright 2002, softSurfer (www.softsurfer.com)
9 // This code may be freely used and modified for any purpose
10 // providing that this copyright notice is included with it.
11 // SoftSurfer makes no warranty for this code, and cannot be held
12 // liable for any real or imagined damage resulting from its use.
13 // Users of this code must verify correctness for their application.
14 /****************************************************************************/
15 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
16 // Copyright (C) 2004-2017 DLR (http://www.dlr.de/) and contributors
17 /****************************************************************************/
18 //
19 // This file is part of SUMO.
20 // SUMO is free software: you can redistribute it and/or modify
21 // it under the terms of the GNU General Public License as published by
22 // the Free Software Foundation, either version 3 of the License, or
23 // (at your option) any later version.
24 //
25 /****************************************************************************/
26 
27 
28 // ===========================================================================
29 // included modules
30 // ===========================================================================
31 #ifdef _MSC_VER
32 #include <windows_config.h>
33 #else
34 #include <config.h>
35 #endif
36 
37 #include "Helper_ConvexHull.h"
38 
39 
41 #include <iostream>
42 
43 
44 // Assume that a class is already given for the object:
45 // Position with coordinates {double x, y;}
48  if (V.size() < 3) {
49  throw ProcessError();
50  }
51  // initialize a deque D[] from bottom to top so that the
52  // 1st three vertices of V[] are a counterclockwise triangle
53  int n = (int) V.size();
54  std::vector<Position> D(2 * n + 1);
55  int bot = n - 2, top = bot + 3; // initial bottom and top deque indices
56  D[bot] = D[top] = V[2]; // 3rd vertex is at both bot and top
57  if (isLeft(V[0], V[1], V[2]) > 0) {
58  D[bot + 1] = V[0];
59  D[bot + 2] = V[1]; // ccw vertices are: 2,0,1,2
60  } else {
61  D[bot + 1] = V[1];
62  D[bot + 2] = V[0]; // ccw vertices are: 2,1,0,2
63  }
64 
65  // compute the hull on the deque D[]
66  for (int i = 3; i < n; i++) { // process the rest of vertices
67  // test if next vertex is inside the deque hull
68  if (bot >= (int) D.size() || top - 1 >= (int) D.size() || i >= (int) V.size()) {
69  throw ProcessError();
70  }
71  if ((isLeft(D[bot], D[bot + 1], V[i]) > 0) &&
72  (isLeft(D[top - 1], D[top], V[i]) > 0)) {
73  continue; // skip an interior vertex
74  }
75 
76  // incrementally add an exterior vertex to the deque hull
77  // get the rightmost tangent at the deque bot
78  while (isLeft(D[bot], D[bot + 1], V[i]) <= 0) {
79  ++bot; // remove bot of deque
80  if (bot >= (int) D.size()) {
81  throw ProcessError();
82  }
83  }
84  if (bot == 0) {
85  throw ProcessError();
86  }
87  D[--bot] = V[i]; // insert V[i] at bot of deque
88 
89  if (top == 0 || top >= (int) D.size()) {
90  throw ProcessError();
91  }
92  // get the leftmost tangent at the deque top
93  while (isLeft(D[top - 1], D[top], V[i]) <= 0) {
94  --top; // pop top of deque
95  if (top == 0 || top >= (int) D.size()) {
96  throw ProcessError();
97  }
98  }
99 
100  if (top + 1 >= (int) D.size()) {
101  throw ProcessError();
102  }
103  D[++top] = V[i]; // push V[i] onto top of deque
104  }
105 
106  // transcribe deque D[] to the output hull array H[]
107  int h; // hull vertex counter
108  PositionVector H;
109  for (h = 0; h <= (top - bot); h++) {
110  if (bot + h >= (int) D.size()) {
111  throw ProcessError();
112  }
113  H.push_back_noDoublePos(D[bot + h]);
114  }
115  return H;
116 }
117 
118 
119 
120 /****************************************************************************/
121 
A list of positions.
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)