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