Line data    Source code

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