SUMO - Simulation of Urban MObility
NBContHelper.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-2017 German Aerospace Center (DLR) and others.
4 /****************************************************************************/
5 //
6 // This program and the accompanying materials
7 // are made available under the terms of the Eclipse Public License v2.0
8 // which accompanies this distribution, and is available at
9 // http://www.eclipse.org/legal/epl-v20.html
10 //
11 /****************************************************************************/
19 // Some methods for traversing lists of edges
20 /****************************************************************************/
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #ifdef _MSC_VER
27 #include <windows_config.h>
28 #else
29 #include <config.h>
30 #endif
31 
32 #include <vector>
33 #include <map>
34 #include <cassert>
35 #include "NBContHelper.h"
36 #include <utils/geom/GeomHelper.h>
37 
38 
39 // ===========================================================================
40 // method definitions
41 // ===========================================================================
42 /* -------------------------------------------------------------------------
43  * utility methods
44  * ----------------------------------------------------------------------- */
45 void
46 NBContHelper::nextCW(const EdgeVector& edges, EdgeVector::const_iterator& from) {
47  from++;
48  if (from == edges.end()) {
49  from = edges.begin();
50  }
51 }
52 
53 
54 void
55 NBContHelper::nextCCW(const EdgeVector& edges, EdgeVector::const_iterator& from) {
56  if (from == edges.begin()) {
57  from = edges.end() - 1;
58  } else {
59  --from;
60  }
61 }
62 
63 
64 std::ostream&
65 NBContHelper::out(std::ostream& os, const std::vector<bool>& v) {
66  for (std::vector<bool>::const_iterator i = v.begin(); i != v.end(); i++) {
67  os << *i;
68  }
69  return os;
70 }
71 
72 
73 NBEdge*
75  NBNode* from, NBNode* to) {
76  for (EdgeVector::const_iterator i = edges.begin(); i != edges.end(); i++) {
77  if ((*i)->getToNode() == to && (*i)->getFromNode() == from) {
78  return *i;
79  }
80  }
81  return 0;
82 }
83 
84 
85 
86 double
88  assert(ev.size() > 0);
89  double max = (*(ev.begin()))->getSpeed();
90  for (EdgeVector::const_iterator i = ev.begin() + 1; i != ev.end(); i++) {
91  max =
92  max > (*i)->getSpeed()
93  ? max : (*i)->getSpeed();
94  }
95  return max;
96 }
97 
98 
99 
100 /* -------------------------------------------------------------------------
101  * methods from node_with_incoming_finder
102  * ----------------------------------------------------------------------- */
104  : myEdge(e) {}
105 
106 
107 bool
109  const EdgeVector& incoming = n->getIncomingEdges();
110  return std::find(incoming.begin(), incoming.end(), myEdge) != incoming.end();
111 }
112 
113 
114 
115 /* -------------------------------------------------------------------------
116  * methods from node_with_outgoing_finder
117  * ----------------------------------------------------------------------- */
119  : myEdge(e) {}
120 
121 
122 bool
124  const EdgeVector& outgoing = n->getOutgoingEdges();
125  return std::find(outgoing.begin(), outgoing.end(), myEdge) != outgoing.end();
126 }
127 
128 
129 
130 /* -------------------------------------------------------------------------
131  * methods from edge_with_destination_finder
132  * ----------------------------------------------------------------------- */
134  : myDestinationNode(dest) {}
135 
136 
137 bool
139  return e->getToNode() == myDestinationNode;
140 }
141 
142 /* -------------------------------------------------------------------------
143  * methods from relative_outgoing_edge_sorter
144  * ----------------------------------------------------------------------- */
145 int
147  if (e1 == 0 || e2 == 0) {
148  return -1;
149  }
150  double relAngle1 = NBHelpers::normRelAngle(
151  myEdge->getEndAngle(), e1->getStartAngle());
152  double relAngle2 = NBHelpers::normRelAngle(
153  myEdge->getEndAngle(), e2->getStartAngle());
154 
155  double lookAhead = 2 * NBEdge::ANGLE_LOOKAHEAD;
156  while (fabs(relAngle1 - relAngle2) < 3.0) {
157  // look at further geometry segments to resolve ambiguity
158  const Position referencePos1 = e1->getGeometry().positionAtOffset2D(lookAhead);
159  const Position referencePos2 = e2->getGeometry().positionAtOffset2D(lookAhead);
160  relAngle1 = NBHelpers::normRelAngle(myEdge->getEndAngle(), GeomHelper::legacyDegree(
161  e1->getFromNode()->getPosition().angleTo2D(referencePos1), true));
162  relAngle2 = NBHelpers::normRelAngle(myEdge->getEndAngle(), GeomHelper::legacyDegree(
163  e2->getFromNode()->getPosition().angleTo2D(referencePos2), true));
164  if (lookAhead > MAX2(e1->getLength(), e2->getLength())) {
165  break;
166  }
167  lookAhead *= 2;
168  }
169  return relAngle1 > relAngle2;
170 }
171 
172 
173 /* -------------------------------------------------------------------------
174  * methods from straightness_sorter
175  * ----------------------------------------------------------------------- */
176 int
178  if (e1 == 0 || e2 == 0) {
179  return -1;
180  }
181  double relAngle1 = NBHelpers::normRelAngle(
182  myReferenceAngle, myRefIncoming ? e1->getShapeStartAngle() : e1->getShapeEndAngle());
183  double relAngle2 = NBHelpers::normRelAngle(
184  myReferenceAngle, myRefIncoming ? e2->getShapeStartAngle() : e2->getShapeEndAngle());
185  const int geomIndex = myRefIncoming ? 0 : -1;
186 
187  //std::cout << " e1=" << e1->getID() << " e2=" << e2->getID() << " refA=" << myReferenceAngle << " initially a1=" << relAngle1 << " a2=" << relAngle2 << "\n";
188  const double e1Length = e1->getGeometry().length2D();
189  const double e2Length = e2->getGeometry().length2D();
190  const double maxLookAhead = MAX2(e1Length, e2Length);
191  double lookAhead = MIN2(maxLookAhead, 2 * NBEdge::ANGLE_LOOKAHEAD);
192  while (fabs(relAngle1 - relAngle2) < 3.0) {
193  // look at further geometry segments to resolve ambiguity
194  const double offset1 = myRefIncoming ? lookAhead : e1Length - lookAhead;
195  const double offset2 = myRefIncoming ? lookAhead : e2Length - lookAhead;
196  const Position referencePos1 = e1->getGeometry().positionAtOffset2D(offset1);
197  const Position referencePos2 = e2->getGeometry().positionAtOffset2D(offset2);
198 
199  relAngle1 = NBHelpers::normRelAngle(myReferenceAngle, GeomHelper::legacyDegree(
200  e1->getGeometry()[geomIndex].angleTo2D(referencePos1), true));
201  relAngle2 = NBHelpers::normRelAngle(myReferenceAngle, GeomHelper::legacyDegree(
202  e2->getGeometry()[geomIndex].angleTo2D(referencePos2), true));
203 
204  if (lookAhead > maxLookAhead) {
205  break;
206  }
207  lookAhead *= 2;
208  }
209  if (fabs(relAngle1 - relAngle2) < 3.0) {
210  // use angle to end of reference edge as tiebraker
211  relAngle1 = NBHelpers::normRelAngle(myReferenceAngle, GeomHelper::legacyDegree(
212  myReferencePos.angleTo2D(e1->getLaneShape(0)[geomIndex]), true));
213  relAngle2 = NBHelpers::normRelAngle(myReferenceAngle, GeomHelper::legacyDegree(
214  myReferencePos.angleTo2D(e2->getLaneShape(0)[geomIndex]), true));
215  //std::cout << " tiebraker refPos=" << myReferencePos << " abs1="
216  // << GeomHelper::legacyDegree(myReferencePos.angleTo2D(e1->getLaneShape(0).front()), true)
217  // << " abs2=" << GeomHelper::legacyDegree(myReferencePos.angleTo2D(e2->getLaneShape(0).front()), true) << "\n";
218  }
219  //std::cout << " e1=" << e1->getID() << " e2=" << e2->getID() << " a1=" << relAngle1 << " a2=" << relAngle2 << "\n";
220  return fabs(relAngle1) < fabs(relAngle2);
221 }
222 
223 
224 /* -------------------------------------------------------------------------
225  * methods from relative_incoming_edge_sorter
226  * ----------------------------------------------------------------------- */
227 int
229  if (e1 == 0 || e2 == 0) {
230  return -1;
231  }
232  double relAngle1 = NBHelpers::normRelAngle(
233  myEdge->getStartAngle(), e1->getEndAngle());
234  double relAngle2 = NBHelpers::normRelAngle(
235  myEdge->getStartAngle(), e2->getEndAngle());
236 
237  double lookAhead = 2 * NBEdge::ANGLE_LOOKAHEAD;
238  while (fabs(relAngle1 - relAngle2) < 3.0) {
239  // look at further geometry segments to resolve ambiguity
240  const Position referencePos1 = e1->getGeometry().positionAtOffset2D(e1->getGeometry().length() - lookAhead);
241  const Position referencePos2 = e2->getGeometry().positionAtOffset2D(e2->getGeometry().length() - lookAhead);
242  relAngle1 = NBHelpers::normRelAngle(myEdge->getStartAngle(), GeomHelper::legacyDegree(
243  referencePos1.angleTo2D(e1->getToNode()->getPosition()), true));
244  relAngle2 = NBHelpers::normRelAngle(myEdge->getStartAngle(), GeomHelper::legacyDegree(
245  referencePos2.angleTo2D(e2->getToNode()->getPosition()), true));
246  if (lookAhead > MAX2(e1->getLength(), e2->getLength())) {
247  break;
248  }
249  lookAhead *= 2;
250  }
251  return relAngle1 > relAngle2;
252 }
253 
254 
255 std::ostream&
256 operator<<(std::ostream& os, const EdgeVector& ev) {
257  for (EdgeVector::const_iterator i = ev.begin(); i != ev.end(); i++) {
258  if (i != ev.begin()) {
259  os << ", ";
260  }
261  os << (*i)->getID();
262  }
263  return os;
264 }
265 
266 
267 
268 
269 double
271  if (edges.size() == 0) {
272  return -1;
273  }
274  double ret = (*(edges.begin()))->getSpeed();
275  for (EdgeVector::const_iterator i = edges.begin() + 1; i != edges.end(); i++) {
276  if ((*i)->getSpeed() > ret) {
277  ret = (*i)->getSpeed();
278  }
279  }
280  return ret;
281 }
282 
283 
284 double
286  if (edges.size() == 0) {
287  return -1;
288  }
289  double ret = (*(edges.begin()))->getSpeed();
290  for (EdgeVector::const_iterator i = edges.begin() + 1; i != edges.end(); i++) {
291  if ((*i)->getSpeed() < ret) {
292  ret = (*i)->getSpeed();
293  }
294  }
295  return ret;
296 }
297 
298 
299 int
301  assert(e1->getFromNode() == myNode || e1->getToNode() == myNode);
302  assert(e2->getFromNode() == myNode || e2->getToNode() == myNode);
303  const double angle1 = e1->getAngleAtNodeToCenter(myNode);
304  const double angle2 = e2->getAngleAtNodeToCenter(myNode);
305  const double absDiff = fabs(angle1 - angle2);
306 
307  // cannot trust the angle difference hence a heuristic:
308  if (absDiff < 2 || absDiff > (360 - 2)) {
309  const bool sameDir = ((e1->getFromNode() == myNode && e2->getFromNode() == myNode)
310  || (e1->getToNode() == myNode && e2->getToNode() == myNode));
311  if (sameDir) {
312  // put edges that allow pedestrians on the 'outside', but be aware if both allow / disallow
313  const bool e1Peds = (e1->getPermissions() & SVC_PEDESTRIAN) != 0;
314  const bool e2Peds = (e2->getPermissions() & SVC_PEDESTRIAN) != 0;
315  if (e1->getToNode() == myNode) {
316  if (e1Peds && !e2Peds) {
317  return true;
318  } else if (!e1Peds && e2Peds) {
319  return false;
320  }
321  } else {
322  if (!e1Peds && e2Peds) {
323  return true;
324  } else if (e1Peds && !e2Peds) {
325  return false;
326  }
327  }
328  // break ties to ensure strictly weak ordering
329  return e1->getID() < e2->getID();
330  } else {
331  // sort incoming before outgoing, no need to break ties here
332  return e1->getToNode() == myNode;
333  }
334  }
335  return angle1 < angle2;
336 }
337 
338 /****************************************************************************/
339 
bool operator()(const NBNode *const n) const
double getLength() const
Returns the computed length of the edge.
Definition: NBEdge.h:480
double getAngleAtNodeToCenter(const NBNode *const node) const
Returns the angle of from the node shape center to where the edge meets the node shape.
Definition: NBEdge.cpp:1623
double length2D() const
Returns the length.
node_with_outgoing_finder(const NBEdge *const e)
constructor
static double maxSpeed(const EdgeVector &ev)
is a pedestrian
static double getMinSpeed(const EdgeVector &edges)
static double normRelAngle(double angle1, double angle2)
ensure that reverse relAngles (>=179.999) always count as turnarounds (-180)
Definition: NBHelpers.cpp:66
Position positionAtOffset2D(double pos, double lateralOffset=0) const
Returns the position at the given length.
static const double ANGLE_LOOKAHEAD
the distance at which to take the default angle
Definition: NBEdge.h:275
friend std::ostream & operator<<(std::ostream &os, const EdgeVector &ev)
The representation of a single edge during network building.
Definition: NBEdge.h:70
int operator()(const NBEdge *e1, const NBEdge *e2) const
comparing operation
int operator()(NBEdge *e1, NBEdge *e2) const
comparing operation
double angleTo2D(const Position &other) const
returns the angle in the plane of the vector pointing from here to the other position ...
Definition: Position.h:259
T MAX2(T a, T b)
Definition: StdDefs.h:73
static void nextCW(const EdgeVector &edges, EdgeVector::const_iterator &from)
const std::string & getID() const
Returns the id.
Definition: Named.h:74
double getShapeStartAngle() const
Returns the angle at the start of the edge.
Definition: NBEdge.cpp:1754
static double legacyDegree(const double angle, const bool positive=false)
Definition: GeomHelper.cpp:205
const EdgeVector & getOutgoingEdges() const
Returns this node&#39;s outgoing edges (The edges which start at this node)
Definition: NBNode.h:254
static std::ostream & out(std::ostream &os, const std::vector< bool > &v)
A point in 2D or 3D with translation and scaling methods.
Definition: Position.h:45
bool operator()(const NBNode *const n) const
T MIN2(T a, T b)
Definition: StdDefs.h:67
int operator()(NBEdge *e1, NBEdge *e2) const
comparing operation
SVCPermissions getPermissions(int lane=-1) const
get the union of allowed classes over all lanes or for a specific lane
Definition: NBEdge.cpp:3025
edge_with_destination_finder(NBNode *dest)
constructor
const PositionVector & getGeometry() const
Returns the geometry of the edge.
Definition: NBEdge.h:602
int operator()(NBEdge *e1, NBEdge *e2) const
comparing operation
double length() const
Returns the length.
const PositionVector & getLaneShape(int i) const
Returns the shape of the nth lane.
Definition: NBEdge.cpp:778
const EdgeVector & getIncomingEdges() const
Returns this node&#39;s incoming edges (The edges which yield in this node)
Definition: NBNode.h:249
std::vector< NBEdge * > EdgeVector
container for (sorted) edges
Definition: NBCont.h:40
double getStartAngle() const
Returns the angle at the start of the edge (relative to the node shape center) The angle is computed ...
Definition: NBEdge.h:442
node_with_incoming_finder(const NBEdge *const e)
constructor
const Position & getPosition() const
Definition: NBNode.h:241
Represents a single node (junction) during network building.
Definition: NBNode.h:74
static double getMaxSpeed(const EdgeVector &edges)
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:426
double getShapeEndAngle() const
Returns the angle at the end of the edge.
Definition: NBEdge.cpp:1762
NBNode * getToNode() const
Returns the destination node of the edge.
Definition: NBEdge.h:433
static void nextCCW(const EdgeVector &edges, EdgeVector::const_iterator &from)
double getEndAngle() const
Returns the angle at the end of the edge (relative to the node shape center) The angle is computed in...
Definition: NBEdge.h:451
static NBEdge * findConnectingEdge(const EdgeVector &edges, NBNode *from, NBNode *to)