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    NGRandomNetBuilder.cpp
      15             : /// @author  Markus Hartinger
      16             : /// @author  Daniel Krajzewicz
      17             : /// @author  Michael Behrisch
      18             : /// @date    Mar, 2003
      19             : ///
      20             : // Additional structures for building random nets
      21             : /****************************************************************************/
      22             : #include <config.h>
      23             : 
      24             : #include <iostream>
      25             : #include <cmath>
      26             : #include <stdlib.h>
      27             : #include "NGRandomNetBuilder.h"
      28             : #include <utils/geom/GeomHelper.h>
      29             : #include <utils/common/StdDefs.h>
      30             : #include <utils/common/RandHelper.h>
      31             : 
      32             : 
      33             : // ===========================================================================
      34             : // method definitions
      35             : // ===========================================================================
      36             : // ---------------------------------------------------------------------------
      37             : // NGRandomNetBuilder-definitions
      38             : // ---------------------------------------------------------------------------
      39          24 : NGRandomNetBuilder::NGRandomNetBuilder(NGNet& net, double minAngle, double minDistance,
      40             :                                        double maxDistance, double connectivity,
      41          24 :                                        int numTries, const RandomDistributor<int>& neighborDist)
      42          24 :     : myNet(net), myMinLinkAngle(minAngle), myMinDistance(minDistance),
      43          24 :       myMaxDistance(maxDistance), myConnectivity(connectivity), myNumTries(numTries),
      44          24 :       myNeighbourDistribution(neighborDist) {
      45          24 : }
      46             : 
      47             : 
      48             : void
      49        1657 : NGRandomNetBuilder::removeOuterNode(NGNode* node) {
      50       60984 :     for (NGNodeList::iterator ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
      51       60984 :         if (*ni == node) {
      52        1657 :             myOuterNodes.erase(ni);
      53             :             return;
      54             :         }
      55             :     }
      56             : }
      57             : 
      58             : 
      59             : bool
      60       91617 : NGRandomNetBuilder::checkAngles(const NGNode* const node) {
      61             :     bool check = true;
      62             : 
      63       91617 :     if (node->getLinks().size() >  1) {
      64             :         // loop over all links
      65             :         NGNode* ni;
      66      262944 :         for (NGEdge* const li : node->getLinks()) {
      67             :             // calc vector of currentnode
      68      198288 :             if (li->getStartNode() == node) {
      69             :                 ni = li->getEndNode();
      70             :             } else {
      71             :                 ni = li->getStartNode();
      72             :             }
      73             :             Position v1(
      74             :                 ni->getPosition().x() - node->getPosition().x(),
      75      198288 :                 ni->getPosition().y() - node->getPosition().y());
      76             :             // loop over all links
      77      876170 :             for (NGEdge* const lj : node->getLinks()) {
      78      677882 :                 if (li != lj) {
      79      479594 :                     if (lj->getStartNode() == node) {
      80             :                         ni = lj->getEndNode();
      81             :                     } else {
      82             :                         ni = lj->getStartNode();
      83             :                     }
      84             :                     Position v2(
      85             :                         ni->getPosition().x() - node->getPosition().x(),
      86      479594 :                         ni->getPosition().y() - node->getPosition().y());
      87      479594 :                     if (fabs(GeomHelper::angle2D(v1, v2)) < myMinLinkAngle) {
      88             :                         check = false;
      89             :                     }
      90             :                 }
      91             :             }
      92             :         }
      93             :     }
      94       91617 :     return check;
      95             : }
      96             : 
      97             : 
      98             : bool
      99      453348 : NGRandomNetBuilder::canConnect(NGNode* baseNode, NGNode* newNode) {
     100             :     bool connectable = true;
     101      453348 :     const PositionVector n(baseNode->getPosition(), newNode->getPosition());
     102             : 
     103             :     // check for range between Basenode and Newnode
     104             :     if (connectable) {
     105      453348 :         double dist = n.length();
     106      453348 :         if ((dist < myMinDistance) || (dist > myMaxDistance)) {
     107             :             connectable = false;
     108             :         }
     109             :     }
     110             : 
     111             :     // check for angle restrictions
     112             :     if (connectable) {
     113       57913 :         connectable = checkAngles(baseNode);
     114             :     }
     115      453348 :     if (connectable) {
     116       33704 :         connectable = checkAngles(newNode);
     117             :     }
     118             : 
     119             :     // check for intersections and range restrictions with outer links
     120      453348 :     if (connectable) {
     121             :         NGEdgeList::iterator li;
     122             :         li = myOuterLinks.begin();
     123     3316104 :         while (connectable && (li != myOuterLinks.end())) {
     124             :             // check intersection only if links don't share a node
     125     3285358 :             const NGNode* const start = (*li)->getStartNode();
     126             :             const NGNode* const end = (*li)->getEndNode();
     127             :             const Position& p1 = start->getPosition();
     128             :             const Position& p2 = end->getPosition();
     129     3285358 :             if ((baseNode != start) && (baseNode != end) && (newNode != start) && (newNode != end)) {
     130     3217328 :                 connectable = !n.intersects(p1, p2);
     131             :             }
     132             :             // check NewNode-To-Links distance only, if NewNode isn't part of link
     133     3285358 :             if (connectable && (newNode != start) && (newNode != end)) {
     134     3250938 :                 const double offset = GeomHelper::nearest_offset_on_line_to_point2D(p1, p2, n[1]);
     135     3250938 :                 if (offset != GeomHelper::INVALID_OFFSET) {
     136      265467 :                     const Position p = PositionVector(p1, p2).positionAtOffset2D(offset);
     137      265467 :                     const double dist = p.distanceTo2D(n[1]);
     138      265467 :                     if (dist < myMinDistance) {
     139             :                         connectable = false;
     140             :                     }
     141             :                 }
     142             :             }
     143             :             ++li;
     144             :         }
     145             :     }
     146      453348 :     return connectable;
     147      453348 : }
     148             : 
     149             : 
     150             : void
     151       11740 : NGRandomNetBuilder::findPossibleOuterNodes(NGNode* node) {
     152       11740 :     myConNodes.clear();
     153             :     NGNodeList::iterator ni;
     154      430412 :     for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
     155      418672 :         NGNode* on = *ni;
     156      418672 :         if (!node->connected(on)) {
     157      412499 :             if ((node->getMaxNeighbours() > (int)node->getLinks().size()) &&
     158      412499 :                     (on->getMaxNeighbours() > (int)on->getLinks().size())) {
     159      412499 :                 if (canConnect(node, on)) {
     160             :                     myConNodes.push_back(on);
     161             :                 }
     162             :             }
     163             :         }
     164             :     }
     165       11740 : }
     166             : 
     167             : 
     168             : bool
     169       32482 : NGRandomNetBuilder::createNewNode(NGNode* baseNode, bool gridMode) {
     170             :     // calculate position of new node based on BaseNode
     171       32482 :     double dist = RandHelper::rand(myMinDistance, myMaxDistance);
     172             :     double angle = RandHelper::rand((double)(2 * M_PI));
     173       32482 :     if (gridMode) {
     174             :         // dist must be a multiple of minDist
     175        7341 :         dist = MAX2(1, int(dist / myMinDistance)) * myMinDistance;
     176             :         // angle must be a multiple of 90 degrees
     177        7341 :         angle = RandHelper::rand(4) * 0.5 * M_PI;
     178             :     }
     179       32482 :     double x = baseNode->getPosition().x() + dist * cos(angle);
     180       32482 :     double y = baseNode->getPosition().y() + dist * sin(angle);
     181       32482 :     NGNode* newNode = new NGNode(myNet.getNextFreeID());
     182             :     newNode->setX(x);
     183             :     newNode->setY(y);
     184       32482 :     newNode->setMaxNeighbours(myNeighbourDistribution.get());
     185       32482 :     NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
     186       32482 :     if (canConnect(baseNode, newNode)) {
     187             :         // add node
     188        2998 :         myNet.add(newNode);
     189        2998 :         myOuterNodes.push_front(newNode);
     190             :         // add link
     191        2998 :         myNet.add(newLink);
     192        2998 :         myOuterLinks.push_back(newLink);
     193             :         // check basenode for being outer node
     194        2998 :         if ((int)baseNode->getLinks().size() >= baseNode->getMaxNeighbours()) {
     195        1238 :             removeOuterNode(baseNode);
     196             :         }
     197        2998 :         return true;
     198             :     } else {
     199       29484 :         delete newLink;
     200       29484 :         delete newNode;
     201       29484 :         return false;
     202             :     }
     203             : }
     204             : 
     205             : 
     206             : void
     207          24 : NGRandomNetBuilder::createNet(int numNodes, bool gridMode) {
     208          24 :     myNumNodes = numNodes;
     209             : 
     210          24 :     NGNode* outerNode = new NGNode(myNet.getNextFreeID());
     211             :     outerNode->setX(0);
     212             :     outerNode->setY(0);
     213             :     outerNode->setMaxNeighbours(4);
     214             : 
     215          24 :     myNet.add(outerNode);
     216          24 :     myOuterNodes.push_back(outerNode);
     217             : 
     218             :     bool created = true;
     219       11764 :     while ((myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
     220             :         // brings last element to front
     221       11740 :         if (!created) {
     222             :             myOuterNodes.push_front(myOuterNodes.back());
     223        7562 :             myOuterNodes.pop_back();
     224             :         }
     225       11740 :         outerNode = myOuterNodes.back();
     226       11740 :         findPossibleOuterNodes(outerNode);
     227             :         created = false;
     228       11740 :         if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
     229             :             // create link
     230        8367 :             NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
     231        8367 :             if (canConnect(outerNode, myConNodes.back())) {
     232             :                 // add link
     233        1180 :                 myNet.add(newLink);
     234        1180 :                 myOuterLinks.push_back(newLink);
     235             :                 // check nodes for being outer node
     236        1180 :                 if ((int)outerNode->getLinks().size() >= outerNode->getMaxNeighbours()) {
     237         256 :                     removeOuterNode(outerNode);
     238             :                 }
     239        1180 :                 if ((int)myConNodes.back()->getLinks().size() >= myConNodes.back()->getMaxNeighbours()) {
     240         163 :                     removeOuterNode(myConNodes.back());
     241             :                 }
     242             :                 created = true;
     243             :             } else {
     244        7187 :                 delete newLink;
     245             :             }
     246             :         } else {
     247             :             int count = 0;
     248             :             do {
     249       32482 :                 created = createNewNode(outerNode, gridMode);
     250       32482 :                 count++;
     251       32482 :             } while ((count <= myNumTries) && !created);
     252        3373 :             if (!created) {
     253         375 :                 outerNode->setMaxNeighbours((int)outerNode->getLinks().size());
     254         375 :                 myOuterNodes.remove(outerNode);
     255             :             }
     256             :         }
     257             :     }
     258          24 : }
     259             : 
     260             : 
     261             : /****************************************************************************/