Line data    Source code

       1             : /****************************************************************************/
       2             : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
       3             : // Copyright (C) 2012-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    NBAlgorithms.h
      15             : /// @author  Daniel Krajzewicz
      16             : /// @author  Jakob Erdmann
      17             : /// @date    02. March 2012
      18             : ///
      19             : // Algorithms for network computation
      20             : /****************************************************************************/
      21             : #pragma once
      22             : #include <config.h>
      23             : 
      24             : #include <map>
      25             : #include "NBEdgeCont.h"
      26             : #include "NBNodeCont.h"
      27             : 
      28             : // ===========================================================================
      29             : // class declarations
      30             : // ===========================================================================
      31             : class NBEdge;
      32             : class NBNode;
      33             : 
      34             : // ===========================================================================
      35             : // class definitions
      36             : // ===========================================================================
      37             : // ---------------------------------------------------------------------------
      38             : // NBTurningDirectionsComputer
      39             : // ---------------------------------------------------------------------------
      40             : /* @class NBTurningDirectionsComputer
      41             :  * @brief Computes turnaround destinations for all edges (if exist)
      42             :  */
      43             : class NBTurningDirectionsComputer {
      44             : public:
      45             :     /** @brief Computes turnaround destinations for all edges (if exist)
      46             :      * @param[in] nc The container of nodes to loop along
      47             :      * @param[in] warn Whether warnings shall be issued
      48             :      */
      49             :     static void computeTurnDirections(NBNodeCont& nc, bool warn = true);
      50             : 
      51             :     /** @brief Computes turnaround destinations for all incoming edges of the given nodes (if any)
      52             :      * @param[in] node The node for which to compute turnaround destinations
      53             :      * @param[in] warn Whether warnings shall be issued
      54             :      * @note: This is needed by netedit
      55             :      */
      56             :     static void computeTurnDirectionsForNode(NBNode* node, bool warn);
      57             : 
      58             :     /// @brief compute angle to junction at a point further away
      59             :     static double getFarAngleAtNode(const NBEdge* e, const NBNode* n, double dist = 50);
      60             : 
      61             : private:
      62             :     /** @struct Combination
      63             :      * @brief Stores the information about the angle between an incoming ("from") and an outgoing ("to") edge
      64             :      *
      65             :      * Note that the angle is increased by 360 if the edges connect the same two nodes in
      66             :      *  opposite direction.
      67             :      */
      68             :     struct Combination {
      69             :         NBEdge* from;
      70             :         NBEdge* to;
      71             :         double angle;
      72             :     };
      73             : 
      74             : 
      75             :     /** @class combination_by_angle_sorter
      76             :      * @brief Sorts "Combination"s by decreasing angle
      77             :      */
      78             :     class combination_by_angle_sorter {
      79             :     public:
      80             :         explicit combination_by_angle_sorter() { }
      81      351555 :         int operator()(const Combination& c1, const Combination& c2) const {
      82      351555 :             if (c1.angle != c2.angle) {
      83       98885 :                 return c1.angle > c2.angle;
      84             :             }
      85      252670 :             if (c1.from != c2.from) {
      86      252044 :                 if (c1.to == c2.to && c1.from->getPermissions() != c2.from->getPermissions()) {
      87         348 :                     if (c1.from->getPermissions() == c1.to->getPermissions()) {
      88             :                         return true;
      89         278 :                     } else if (c2.from->getPermissions() == c1.to->getPermissions()) {
      90             :                         return false;
      91             :                     }
      92             :                 }
      93      251934 :                 return c1.from->getID() < c2.from->getID();
      94             :             }
      95         626 :             if (c1.to->getPermissions() != c2.to->getPermissions()) {
      96         390 :                 if (c1.to->getPermissions() == c1.from->getPermissions()) {
      97             :                     return true;
      98         318 :                 } else if (c2.to->getPermissions() == c1.from->getPermissions()) {
      99             :                     return false;
     100             :                 }
     101             :             }
     102         530 :             return c1.to->getID() < c2.to->getID();
     103             :         }
     104             :     };
     105             : };
     106             : 
     107             : 
     108             : 
     109             : // ---------------------------------------------------------------------------
     110             : // NBNodesEdgesSorter
     111             : // ---------------------------------------------------------------------------
     112             : /* @class NBNodesEdgesSorter
     113             :  * @brief Sorts a node's edges clockwise regarding driving direction
     114             :  */
     115             : class NBNodesEdgesSorter {
     116             : public:
     117             :     /** @brief Sorts a node's edges clockwise regarding driving direction
     118             :      * @param[in] nc The container of nodes to loop along
     119             :      * @param[in] useNodeShape Whether to sort based on the node shape (instead of only the edge angle)
     120             :      */
     121             :     static void sortNodesEdges(NBNodeCont& nc, bool useNodeShape = false);
     122             : 
     123             :     /** @class crossing_by_junction_angle_sorter
     124             :      * @brief Sorts crossings by minimum clockwise clockwise edge angle. Use the
     125             :      * ordering found in myAllEdges of the given node
     126             :      */
     127      756042 :     class crossing_by_junction_angle_sorter {
     128             :     public:
     129             :         explicit crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering);
     130             : 
     131        3601 :         int operator()(const std::unique_ptr<NBNode::Crossing>& c1, const std::unique_ptr<NBNode::Crossing>& c2) const {
     132        3601 :             const int r1 = getMinRank(c1->edges);
     133        3601 :             const int r2 = getMinRank(c2->edges);
     134        3601 :             if (r1 == r2) {
     135          38 :                 return c1->edges.size() > c2->edges.size();
     136             :             } else {
     137        3563 :                 return (int)(r1 < r2);
     138             :             }
     139             :         }
     140             : 
     141             :     private:
     142             :         /// @brief retrieves the minimum index in myAllEdges
     143        7202 :         int getMinRank(const EdgeVector& e) const {
     144        7202 :             int result = (int)myOrdering.size();
     145       19487 :             for (EdgeVector::const_iterator it = e.begin(); it != e.end(); ++it) {
     146       12285 :                 int rank = (int)std::distance(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), *it));
     147             :                 result = MIN2(result, rank);
     148             :             }
     149        7202 :             return result;
     150             :         }
     151             : 
     152             :     private:
     153             :         EdgeVector myOrdering;
     154             :     };
     155             : 
     156             :     /** @brief Assures correct order for same-angle opposite-direction edges
     157             :      * @param[in] n The currently processed node
     158             :      * @param[in] i1 Pointer to first edge
     159             :      * @param[in] i2 Pointer to second edge
     160             :      */
     161             :     static void swapWhenReversed(const NBNode* const n,
     162             :                                  const std::vector<NBEdge*>::iterator& i1,
     163             :                                  const std::vector<NBEdge*>::iterator& i2);
     164             : 
     165             : 
     166             :     /** @class edge_by_junction_angle_sorter
     167             :      * @brief Sorts incoming and outgoing edges clockwise around the given node
     168             :      */
     169             :     class edge_by_junction_angle_sorter {
     170             :     public:
     171             :         explicit edge_by_junction_angle_sorter(NBNode* n) : myNode(n) {}
     172     2075098 :         int operator()(NBEdge* e1, NBEdge* e2) const {
     173     2075098 :             const double a1 = e1->getAngleAtNodeNormalized(myNode);
     174     2075098 :             const double a2 = e2->getAngleAtNodeNormalized(myNode);
     175     2075098 :             return a1 < a2 || (a1 == a2 && e1->getNumericalID() < e2->getNumericalID());
     176             :         }
     177             : 
     178             :     private:
     179             :         /// @brief The node to compute the relative angle of
     180             :         NBNode* myNode;
     181             : 
     182             :     };
     183             : 
     184             : };
     185             : 
     186             : 
     187             : 
     188             : // ---------------------------------------------------------------------------
     189             : // NBNodeTypeComputer
     190             : // ---------------------------------------------------------------------------
     191             : /* @class NBNodeTypeComputer
     192             :  * @brief Computes node types
     193             :  */
     194             : class NBNodeTypeComputer {
     195             : public:
     196             :     /** @brief Computes node types
     197             :      * @param[in] nc The container of nodes to loop along
     198             :      */
     199             :     static void computeNodeTypes(NBNodeCont& nc, NBTrafficLightLogicCont& tlc);
     200             : 
     201             :     /** @brief Checks rail_crossing for validity
     202             :      * @param[in] nc The container of nodes to loop along
     203             :      */
     204             :     static void validateRailCrossings(NBNodeCont& nc, NBTrafficLightLogicCont& tlc);
     205             : 
     206             :     /// @brief whether the given node only has rail edges
     207             :     static bool isRailwayNode(const NBNode* n);
     208             : };
     209             : 
     210             : 
     211             : 
     212             : // ---------------------------------------------------------------------------
     213             : // NBEdgePriorityComputer
     214             : // ---------------------------------------------------------------------------
     215             : /* @class NBEdgePriorityComputer
     216             :  * @brief Computes edge priorities within a node
     217             :  */
     218             : class NBEdgePriorityComputer {
     219             : public:
     220             :     /** @brief Computes edge priorities within a node
     221             :      * @param[in] nc The container of nodes to loop along
     222             :      */
     223             :     static void computeEdgePriorities(NBNodeCont& nc);
     224             : 
     225             : private:
     226             :     /** @brief Sets the priorites in case of a priority junction
     227             :      * @param[in] n The node to set edges' priorities
     228             :      */
     229             :     static void setPriorityJunctionPriorities(NBNode& n, bool forceStraight = false);
     230             : 
     231             :     /// @brief score pair of edges for multi-criteria evaluatoin of angle, priority, laneNumber and speed
     232             :     static double getScore(const NBEdge* e1, const NBEdge* e2, int minPrio, int maxPrio, int maxNumLanes, double maxSpeed);
     233             : 
     234             :     /// @brief set priority for edges that are parallel to the best edges
     235             :     static void markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond);
     236             : 
     237             :     /** @brief Sets the priorites in case of a priority junction
     238             :      * @param[in] n The node to set edges' priorities
     239             :      * @param[in] s The vector of edges to get and mark the first from
     240             :      * @param[in] prio The priority to assign
     241             :      * @return The vector's first edge
     242             :      */
     243             :     static NBEdge* extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio = 1);
     244             : 
     245             :     /** @brief Returns whether both edges have the same priority
     246             :      * @param[in] e1 The first edge
     247             :      * @param[in] e2 The second edge
     248             :      * Whether both edges have the same priority
     249             :      */
     250             :     static bool samePriority(const NBEdge* const e1, const NBEdge* const e2);
     251             : 
     252             :     /// @brief return whether the priorite attribute can be used to distinguish the edges
     253             :     static bool hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded);
     254             : 
     255             : };