SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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-2016 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 #ifdef CHECK_MEMORY_LEAKS
44 #include <foreign/nvwa/debug_new.h>
45 #endif // CHECK_MEMORY_LEAKS
46 
47 
48 // Assume that a class is already given for the object:
49 // Position with coordinates {SUMOReal x, y;}
52  if (V.size() < 3) {
53  throw ProcessError();
54  }
55  // initialize a deque D[] from bottom to top so that the
56  // 1st three vertices of V[] are a counterclockwise triangle
57  int n = (int) V.size();
58  std::vector<Position> D(2 * n + 1);
59  int bot = n - 2, top = bot + 3; // initial bottom and top deque indices
60  D[bot] = D[top] = V[2]; // 3rd vertex is at both bot and top
61  if (isLeft(V[0], V[1], V[2]) > 0) {
62  D[bot + 1] = V[0];
63  D[bot + 2] = V[1]; // ccw vertices are: 2,0,1,2
64  } else {
65  D[bot + 1] = V[1];
66  D[bot + 2] = V[0]; // ccw vertices are: 2,1,0,2
67  }
68 
69  // compute the hull on the deque D[]
70  for (int i = 3; i < n; i++) { // process the rest of vertices
71  // test if next vertex is inside the deque hull
72  if (bot >= (int) D.size() || top - 1 >= (int) D.size() || i >= (int) V.size()) {
73  throw ProcessError();
74  }
75  if ((isLeft(D[bot], D[bot + 1], V[i]) > 0) &&
76  (isLeft(D[top - 1], D[top], V[i]) > 0)) {
77  continue; // skip an interior vertex
78  }
79 
80  // incrementally add an exterior vertex to the deque hull
81  // get the rightmost tangent at the deque bot
82  while (isLeft(D[bot], D[bot + 1], V[i]) <= 0) {
83  ++bot; // remove bot of deque
84  if (bot >= (int) D.size()) {
85  throw ProcessError();
86  }
87  }
88  if (bot == 0) {
89  throw ProcessError();
90  }
91  D[--bot] = V[i]; // insert V[i] at bot of deque
92 
93  if (top == 0 || top >= (int) D.size()) {
94  throw ProcessError();
95  }
96  // get the leftmost tangent at the deque top
97  while (isLeft(D[top - 1], D[top], V[i]) <= 0) {
98  --top; // pop top of deque
99  if (top == 0 || top >= (int) D.size()) {
100  throw ProcessError();
101  }
102  }
103 
104  if (top + 1 >= (int) D.size()) {
105  throw ProcessError();
106  }
107  D[++top] = V[i]; // push V[i] onto top of deque
108  }
109 
110  // transcribe deque D[] to the output hull array H[]
111  int h; // hull vertex counter
112  PositionVector H;
113  for (h = 0; h <= (top - bot); h++) {
114  if (bot + h >= (int) D.size()) {
115  throw ProcessError();
116  }
117  H.push_back_noDoublePos(D[bot + h]);
118  }
119  return H;
120 }
121 
122 
123 
124 /****************************************************************************/
125 
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)
insert in back a non double position