1 /****************************************************************************/ 2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo 3 // Copyright (C) 2001-2019 German Aerospace Center (DLR) and others. 4 // This program and the accompanying materials 5 // are made available under the terms of the Eclipse Public License v2.0 6 // which accompanies this distribution, and is available at 7 // http://www.eclipse.org/legal/epl-v20.html 8 // SPDX-License-Identifier: EPL-2.0 9 /****************************************************************************/ 10 /// @file NBContHelper.h 11 /// @author Daniel Krajzewicz 12 /// @author Jakob Erdmann 13 /// @author Michael Behrisch 14 /// @date Mon, 17 Dec 2001 15 /// @version $Id$ 16 /// 17 // Some methods for traversing lists of edges 18 /****************************************************************************/ 19 #ifndef NBContHelper_h 20 #define NBContHelper_h 21 22 23 // =========================================================================== 24 // included modules 25 // =========================================================================== 26 #include <config.h> 27 28 #include <vector> 29 #include <iostream> 30 #include <cmath> 31 #include <algorithm> 32 #include <cassert> 33 #include "NBHelpers.h" 34 #include "NBCont.h" 35 #include "NBEdge.h" 36 #include "NBNode.h" 37 #include <utils/common/StdDefs.h> 38 #include <utils/geom/GeomHelper.h> 39 40 41 // =========================================================================== 42 // class definitions 43 // =========================================================================== 44 /** 45 * NBContHelper 46 * Some static helper methods that traverse a sorted list of edges in both 47 * directions 48 */ 49 class NBContHelper { 50 public: 51 /** Moves the given iterator clockwise within the given container 52 of edges sorted clockwise */ 53 static void nextCW(const EdgeVector& edges, 54 EdgeVector::const_iterator& from); 55 56 /** Moves the given iterator counter clockwise within the given container 57 of edges sorted clockwise */ 58 static void nextCCW(const EdgeVector& edges, 59 EdgeVector::const_iterator& from); 60 61 static double getMaxSpeed(const EdgeVector& edges); 62 63 static double getMinSpeed(const EdgeVector& edges); 64 65 /** writes the vector of bools to the given stream */ 66 static std::ostream& out(std::ostream& os, const std::vector<bool>& v); 67 68 69 /** 70 * relative_outgoing_edge_sorter 71 * Class to sort edges by their angle in relation to the node the 72 * edge using this class is incoming into. This is normally done to 73 * sort edges outgoing from the node the using edge is incoming in 74 * by their angle in relation to the using edge's angle (this angle 75 * is the reference angle). 76 */ 77 class relative_outgoing_edge_sorter { 78 public: 79 /// constructor relative_outgoing_edge_sorter(NBEdge * e)80 explicit relative_outgoing_edge_sorter(NBEdge* e) : myEdge(e) {} 81 82 public: 83 /// comparing operation 84 int operator()(NBEdge* e1, NBEdge* e2) const; 85 86 private: 87 /// the edge to compute the relative angle of 88 NBEdge* myEdge; 89 }; 90 91 92 /** 93 * relative_incoming_edge_sorter 94 * Class to sort edges by their angle in relation to an outgoing edge. 95 * This is normally done to sort edges incoming at the starting node of this edge 96 * by their angle in relation to the using edge's angle (this angle 97 * is the reference angle). 98 */ 99 class relative_incoming_edge_sorter { 100 public: 101 /// constructor relative_incoming_edge_sorter(NBEdge * e)102 explicit relative_incoming_edge_sorter(NBEdge* e) : myEdge(e) {} 103 104 public: 105 /// comparing operation 106 int operator()(NBEdge* e1, NBEdge* e2) const; 107 108 private: 109 /// the edge to compute the relative angle of 110 NBEdge* myEdge; 111 }; 112 113 114 /** 115 * edge_by_priority_sorter 116 * Class to sort edges by their priority 117 */ 118 class edge_by_priority_sorter { 119 public: 120 /// comparing operator operator()121 int operator()(NBEdge* e1, NBEdge* e2) const { 122 if (e1->getPriority() != e2->getPriority()) { 123 return e1->getPriority() > e2->getPriority(); 124 } 125 if (e1->getSpeed() != e2->getSpeed()) { 126 return e1->getSpeed() > e2->getSpeed(); 127 } 128 return e1->getNumLanes() > e2->getNumLanes(); 129 } 130 }; 131 132 // --------------------------- 133 134 /** 135 * @class edge_opposite_direction_sorter 136 * @brief Class to sort edges by their angle in relation to the given edge 137 * 138 * The resulting sorted list has the edge in the most opposite direction 139 * to the given edge as her first entry. 140 */ 141 class edge_opposite_direction_sorter { 142 public: 143 /** @brief Constructor 144 * @param[in] e The edge to which the sorting relates 145 * @param[in] n The node to consider 146 */ edge_opposite_direction_sorter(const NBEdge * const e,const NBNode * const n,bool regardPriority)147 explicit edge_opposite_direction_sorter(const NBEdge* const e, const NBNode* const n, bool regardPriority) : 148 myNode(n), 149 myEdge(e), 150 myRegardPriority(regardPriority) { 151 myAngle = getEdgeAngleAt(e, n); 152 } 153 154 /** @brief Comparing operation 155 * @param[in] e1 The first edge to compare 156 * @param[in] e2 The second edge to compare 157 * @return Which edge is more opposite to the related one 158 */ operator()159 int operator()(NBEdge* e1, NBEdge* e2) const { 160 if (!myRegardPriority || e1->getPriority() == e2->getPriority() || e1 == myEdge || e2 == myEdge) { 161 return getDiff(e1) > getDiff(e2); 162 } else { 163 return e1->getPriority() > e2->getPriority(); 164 } 165 } 166 167 protected: 168 /** @brief Computes the angle difference between the related and the given edge 169 * @param[in] e The edge to compare the angle difference of 170 * @return The angle difference 171 */ getDiff(const NBEdge * const e)172 double getDiff(const NBEdge* const e) const { 173 return fabs(GeomHelper::angleDiff(getEdgeAngleAt(e, myNode), myAngle)); 174 } 175 176 /** @brief Returns the given edge's angle at the given node 177 * 178 * Please note that we always consider the "outgoing direction". 179 * @param[in] e The edge to which the sorting relates 180 * @param[in] n The node to consider 181 */ getEdgeAngleAt(const NBEdge * const e,const NBNode * const n)182 double getEdgeAngleAt(const NBEdge* const e, const NBNode* const n) const { 183 if (e->getFromNode() == n) { 184 return e->getGeometry().angleAt2D(0); 185 } else { 186 return e->getGeometry()[-1].angleTo2D(e->getGeometry()[-2]); 187 } 188 } 189 190 private: 191 192 /// @brief The related node 193 const NBNode* const myNode; 194 195 /// @brief the reference edge 196 const NBEdge* const myEdge; 197 198 /// @brief The angle of the related edge at the given node 199 double myAngle; 200 201 /// @brief Whether edge priority may override closer angles 202 bool myRegardPriority; 203 204 private: 205 /// @brief Invalidated assignment operator 206 edge_opposite_direction_sorter& operator=(const edge_opposite_direction_sorter& s); 207 208 }; 209 210 // --------------------------- 211 212 /** 213 * edge_similar_direction_sorter 214 * Class to sort edges by their angle in relation to the given edge 215 * The resulting list should have the edge in the most similar direction 216 * to the given edge as its first entry 217 */ 218 class edge_similar_direction_sorter { 219 public: 220 /// constructor edge_similar_direction_sorter(const NBEdge * const e)221 explicit edge_similar_direction_sorter(const NBEdge* const e) 222 : myAngle(e->getShapeEndAngle()) {} 223 224 /// comparing operation operator()225 int operator()(const NBEdge* e1, const NBEdge* e2) const { 226 const double d1 = angleDiff(e1->getShapeStartAngle(), myAngle); 227 const double d2 = angleDiff(e2->getShapeStartAngle(), myAngle); 228 if (fabs(fabs(d1) - fabs(d2)) < NUMERICAL_EPS) { 229 if (fabs(d1 - d2) > NUMERICAL_EPS) { 230 return d1 < d2; 231 } else { 232 return e1->getNumericalID() < e2->getNumericalID(); 233 } 234 } 235 return fabs(d1) < fabs(d2); 236 } 237 238 private: angleDiff(const double angle1,const double angle2)239 double angleDiff(const double angle1, const double angle2) const { 240 double d = angle2 - angle1; 241 while (d >= 180.) { 242 d -= 360.; 243 } 244 while (d < -180.) { 245 d += 360.; 246 } 247 return d; 248 } 249 250 251 private: 252 /// the angle to find the edge with the opposite direction 253 double myAngle; 254 }; 255 256 257 /** 258 * @class node_with_incoming_finder 259 */ 260 class node_with_incoming_finder { 261 public: 262 /// constructor 263 node_with_incoming_finder(const NBEdge* const e); 264 265 bool operator()(const NBNode* const n) const; 266 267 private: 268 const NBEdge* const myEdge; 269 270 private: 271 /// @brief invalidated assignment operator 272 node_with_incoming_finder& operator=(const node_with_incoming_finder& s); 273 274 }; 275 276 277 /** 278 * @class node_with_outgoing_finder 279 */ 280 class node_with_outgoing_finder { 281 public: 282 /// constructor 283 node_with_outgoing_finder(const NBEdge* const e); 284 285 bool operator()(const NBNode* const n) const; 286 287 private: 288 const NBEdge* const myEdge; 289 290 private: 291 /// @brief invalidated assignment operator 292 node_with_outgoing_finder& operator=(const node_with_outgoing_finder& s); 293 294 }; 295 296 297 298 299 class edge_with_destination_finder { 300 public: 301 /// constructor 302 edge_with_destination_finder(NBNode* dest); 303 304 bool operator()(NBEdge* e) const; 305 306 private: 307 NBNode* myDestinationNode; 308 309 private: 310 /// @brief invalidated assignment operator 311 edge_with_destination_finder& operator=(const edge_with_destination_finder& s); 312 313 }; 314 315 316 /** Tries to return the first edge within the given container which 317 connects both given nodes */ 318 static NBEdge* findConnectingEdge(const EdgeVector& edges, 319 NBNode* from, NBNode* to); 320 321 322 /** returns the maximum speed allowed on the edges */ 323 static double maxSpeed(const EdgeVector& ev); 324 325 /** 326 * same_connection_edge_sorter 327 * This class is used to sort edges which connect the same nodes. 328 * The edges are sorted in dependence to edges connecting them. The 329 * rightmost will be the first in the list; the leftmost the last one. 330 */ 331 class same_connection_edge_sorter { 332 public: 333 /// constructor same_connection_edge_sorter()334 explicit same_connection_edge_sorter() { } 335 336 /// comparing operation operator()337 int operator()(NBEdge* e1, NBEdge* e2) const { 338 std::pair<double, double> mm1 = getMinMaxRelAngles(e1); 339 std::pair<double, double> mm2 = getMinMaxRelAngles(e2); 340 if (mm1.first == mm2.first && mm1.second == mm2.second) { 341 // ok, let's simply sort them arbitrarily 342 return e1->getID() < e2->getID(); 343 } 344 345 assert( 346 (mm1.first <= mm2.first && mm1.second <= mm2.second) 347 || 348 (mm1.first >= mm2.first && mm1.second >= mm2.second)); 349 return (mm1.first >= mm2.first && mm1.second >= mm2.second); 350 } 351 352 /** 353 * 354 */ getMinMaxRelAngles(NBEdge * e)355 std::pair<double, double> getMinMaxRelAngles(NBEdge* e) const { 356 double min = 360; 357 double max = 360; 358 const EdgeVector& ev = e->getConnectedEdges(); 359 for (EdgeVector::const_iterator i = ev.begin(); i != ev.end(); ++i) { 360 double angle = NBHelpers::normRelAngle( 361 e->getTotalAngle(), (*i)->getTotalAngle()); 362 if (min == 360 || min > angle) { 363 min = angle; 364 } 365 if (max == 360 || max < angle) { 366 max = angle; 367 } 368 } 369 return std::pair<double, double>(min, max); 370 } 371 }; 372 373 374 friend std::ostream& operator<<(std::ostream& os, const EdgeVector& ev); 375 376 class opposite_finder { 377 public: 378 /// constructor opposite_finder(NBEdge * edge)379 opposite_finder(NBEdge* edge) 380 : myReferenceEdge(edge) { } 381 operator()382 bool operator()(NBEdge* e) const { 383 return e->isTurningDirectionAt(myReferenceEdge) || 384 myReferenceEdge->isTurningDirectionAt(e); 385 } 386 387 private: 388 NBEdge* myReferenceEdge; 389 390 }; 391 392 /** 393 * edge_by_angle_to_nodeShapeCentroid_sorter 394 * Class to sort edges by their angle in relation to the node shape 395 * */ 396 class edge_by_angle_to_nodeShapeCentroid_sorter { 397 public: 398 /// constructor edge_by_angle_to_nodeShapeCentroid_sorter(const NBNode * n)399 explicit edge_by_angle_to_nodeShapeCentroid_sorter(const NBNode* n) : myNode(n) {} 400 401 public: 402 /// comparing operation 403 int operator()(const NBEdge* e1, const NBEdge* e2) const; 404 405 private: 406 /// the edge to compute the relative angle of 407 const NBNode* myNode; 408 }; 409 410 }; 411 412 413 #endif 414 415 /****************************************************************************/ 416 417