SUMO - Simulation of Urban MObility
NGRandomNetBuilder.cpp
Go to the documentation of this file.
00001 /****************************************************************************/
00009 // Additional structures for building random nets
00010 /****************************************************************************/
00011 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
00012 // Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors
00013 /****************************************************************************/
00014 //
00015 //   This file is part of SUMO.
00016 //   SUMO is free software: you can redistribute it and/or modify
00017 //   it under the terms of the GNU General Public License as published by
00018 //   the Free Software Foundation, either version 3 of the License, or
00019 //   (at your option) any later version.
00020 //
00021 /****************************************************************************/
00022 
00023 
00024 // ===========================================================================
00025 // included modules
00026 // ===========================================================================
00027 #ifdef _MSC_VER
00028 #include <windows_config.h>
00029 #else
00030 #include <config.h>
00031 #endif
00032 
00033 #include <iostream>
00034 #include <math.h>
00035 #include <stdlib.h>
00036 #include "NGRandomNetBuilder.h"
00037 #include <utils/geom/GeomHelper.h>
00038 #include <utils/common/RandHelper.h>
00039 
00040 #ifdef CHECK_MEMORY_LEAKS
00041 #include <foreign/nvwa/debug_new.h>
00042 #endif // CHECK_MEMORY_LEAKS
00043 
00044 
00045 // ===========================================================================
00046 // method definitions
00047 // ===========================================================================
00048 // ---------------------------------------------------------------------------
00049 // TNeighbourDistribution-definitions
00050 // ---------------------------------------------------------------------------
00051 void
00052 TNeighbourDistribution::add(int NumNeighbours, SUMOReal ratio) {
00053     myNeighbours[NumNeighbours] = ratio;
00054 }
00055 
00056 
00057 int
00058 TNeighbourDistribution::num() {
00059     SUMOReal sum = 0, RandValue;
00060     std::map<int, SUMOReal>::iterator i;
00061     // total sum of ratios
00062     for (i = myNeighbours.begin(); i != myNeighbours.end(); ++i) {
00063         sum += (*i).second;
00064     }
00065     // RandValue = [0,sum]
00066     RandValue = RandHelper::rand(sum);
00067     // find selected item
00068     i = myNeighbours.begin();
00069     sum = (*i).second;
00070     while ((i != myNeighbours.end()) && (sum < RandValue)) {
00071         i++;
00072         sum += (*i).second;
00073     }
00074     return (*i).first;
00075 }
00076 
00077 
00078 // ---------------------------------------------------------------------------
00079 // NGRandomNetBuilder-definitions
00080 // ---------------------------------------------------------------------------
00081 NGRandomNetBuilder::NGRandomNetBuilder(NGNet& net, SUMOReal minAngle, SUMOReal minDistance,
00082                                        SUMOReal maxDistance, SUMOReal connectivity,
00083                                        int numTries, const TNeighbourDistribution& neighborDist)
00084     : myNet(net), myMinLinkAngle(minAngle), myMinDistance(minDistance),
00085       myMaxDistance(maxDistance), myConnectivity(connectivity), myNumTries(numTries),
00086       myNeighbourDistribution(neighborDist) {
00087 }
00088 
00089 
00090 void
00091 NGRandomNetBuilder::removeOuterNode(NGNode* node) {
00092     for (NGNodeList::iterator ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
00093         if (*ni == node) {
00094             myOuterNodes.erase(ni);
00095             return;
00096         }
00097     }
00098 }
00099 
00100 
00101 bool
00102 NGRandomNetBuilder::checkAngles(NGNode* node) {
00103     bool check = true;
00104 
00105     if (node->LinkList.size() >  1) {
00106         // loop over all links
00107         NGEdgeList::iterator li;
00108         NGNode* ni;
00109         for (li = node->LinkList.begin(); li != node->LinkList.end(); ++li) {
00110             // calc vector of currentnode
00111             if ((*li)->getStartNode() == node) {
00112                 ni = (*li)->getEndNode();
00113             } else {
00114                 ni = (*li)->getStartNode();
00115             }
00116             Position v1(
00117                 ni->getPosition().x() - node->getPosition().x(),
00118                 ni->getPosition().y() - node->getPosition().y());
00119             // loop over all links
00120             NGEdgeList::iterator lj;
00121             for (lj = node->LinkList.begin(); lj != node->LinkList.end(); ++lj) {
00122                 if (li != lj) {
00123                     if ((*lj)->getStartNode() == node) {
00124                         ni = (*lj)->getEndNode();
00125                     } else {
00126                         ni = (*lj)->getStartNode();
00127                     }
00128                     Position v2(
00129                         ni->getPosition().x() - node->getPosition().x(),
00130                         ni->getPosition().y() - node->getPosition().y());
00131                     SUMOReal angle = GeomHelper::Angle2D(v1.x(), v1.y(), v2.x(), v2.y());
00132                     if (fabs((SUMOReal) angle) < myMinLinkAngle) {
00133                         check = false;
00134                     }
00135                 }
00136             }
00137         }
00138     }
00139     return check;
00140 }
00141 
00142 
00143 bool
00144 NGRandomNetBuilder::canConnect(NGNode* baseNode, NGNode* newNode) {
00145     bool connectable = true;
00146     Position n1(baseNode->getPosition());
00147     Position n2(newNode->getPosition());
00148 
00149     // check for range between Basenode and Newnode
00150     if (connectable) {
00151         SUMOReal dist = n1.distanceTo(n2);
00152         if ((dist < myMinDistance) || (dist > myMaxDistance)) {
00153             connectable = false;
00154         }
00155     }
00156 
00157     // check for angle restrictions
00158     if (connectable) {
00159         connectable = checkAngles(baseNode);
00160     }
00161     if (connectable) {
00162         connectable = checkAngles(newNode);
00163     }
00164 
00165     // check for intersections and range restrictions with outer links
00166     if (connectable) {
00167         NGEdgeList::iterator li;
00168         li = myOuterLinks.begin();
00169         while ((connectable == true) && (li != myOuterLinks.end())) {
00170             // check intersection only if links don't share a node
00171             Position p1((*li)->getStartNode()->getPosition());
00172             Position p2((*li)->getEndNode()->getPosition());
00173             if ((baseNode != (*li)->getStartNode()) && (baseNode != (*li)->getEndNode())
00174                     && (newNode != (*li)->getStartNode()) && (newNode != (*li)->getEndNode())) {
00175                 connectable = !GeomHelper::intersects(n1, n2, p1, p2);
00176 
00177             }
00178             // check NewNode-To-Links distance only, if NewNode isn't part of link
00179             if ((connectable) &&
00180                     (newNode != (*li)->getStartNode()) && (newNode != (*li)->getEndNode())) {
00181                 SUMOReal dist = GeomHelper::distancePointLine(n2, p1, p2);
00182                 if ((dist < myMinDistance) && (dist > -1)) {
00183                     connectable = false;
00184                 }
00185             }
00186             li++;
00187         }
00188     }
00189     return connectable;
00190 }
00191 
00192 
00193 void
00194 NGRandomNetBuilder::findPossibleOuterNodes(NGNode* node) {
00195     myConNodes.clear();
00196     NGNodeList::iterator ni;
00197     for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
00198         NGNode* on = *ni;
00199         if (!node->connected(on)) {
00200             if ((node->getMaxNeighbours() > node->LinkList.size()) &&
00201                     ((on)->getMaxNeighbours() > (on)->LinkList.size())) {
00202                 if (canConnect(node, on)) {
00203                     myConNodes.push_back(on);
00204                 }
00205             }
00206         }
00207     }
00208 }
00209 
00210 
00211 bool
00212 NGRandomNetBuilder::createNewNode(NGNode* baseNode) {
00213     // calculate position of new node based on BaseNode
00214     SUMOReal dist = RandHelper::rand(myMinDistance, myMaxDistance);
00215     SUMOReal angle = RandHelper::rand((SUMOReal)(2 * PI));
00216     SUMOReal x = baseNode->getPosition().x() + dist * cos(angle);
00217     SUMOReal y = baseNode->getPosition().y() + dist * sin(angle);
00218     NGNode* newNode = new NGNode(myNet.getNextFreeID());
00219     newNode->setX(x);
00220     newNode->setY(y);
00221     newNode->setMaxNeighbours((SUMOReal) myNeighbourDistribution.num());
00222     NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
00223     if (canConnect(baseNode, newNode)) {
00224         // add node
00225         myNet.add(newNode);
00226         myOuterNodes.push_front(newNode);
00227         // add link
00228         myNet.add(newLink);
00229         myOuterLinks.push_back(newLink);
00230         // check basenode for being outer node
00231         if (baseNode->LinkList.size() >= baseNode->getMaxNeighbours()) {
00232             removeOuterNode(baseNode);
00233         }
00234         return true;
00235     } else {
00236         delete newNode;
00237         return false;
00238     }
00239 }
00240 
00241 
00242 void
00243 NGRandomNetBuilder::createNet(int numNodes) {
00244     myNumNodes = numNodes;
00245 
00246     NGNode* outerNode = new NGNode(myNet.getNextFreeID());
00247     outerNode->setX(0);
00248     outerNode->setY(0);
00249     outerNode->setMaxNeighbours(4);
00250 
00251     myNet.add(outerNode);
00252     myOuterNodes.push_back(outerNode);
00253 
00254     bool created = true;
00255     while (((int) myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
00256         // brings last element to front
00257         if (!created) {
00258             myOuterNodes.push_front(myOuterNodes.back());
00259             myOuterNodes.pop_back();
00260         }
00261         outerNode = myOuterNodes.back();
00262         findPossibleOuterNodes(outerNode);
00263         created = false;
00264         if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
00265             // create link
00266             NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
00267             if (canConnect(outerNode, myConNodes.back())) {
00268                 // add link
00269                 myNet.add(newLink);
00270                 myOuterLinks.push_back(newLink);
00271                 // check nodes for being outer node
00272                 if (outerNode->LinkList.size() >= outerNode->getMaxNeighbours()) {
00273                     removeOuterNode(outerNode);
00274                 }
00275                 if (myConNodes.back()->LinkList.size() >= myConNodes.back()->getMaxNeighbours()) {
00276                     removeOuterNode(myConNodes.back());
00277                 }
00278                 created = true;
00279             } else {
00280                 delete newLink;
00281             }
00282         } else {
00283             int count = 0;
00284             do {
00285                 created = createNewNode(outerNode);
00286                 count++;
00287             } while ((count <= myNumTries) && !created);
00288             if (!created) {
00289                 outerNode->setMaxNeighbours((SUMOReal) outerNode->LinkList.size());
00290                 myOuterNodes.remove(outerNode);
00291             }
00292         }
00293     }
00294 }
00295 
00296 
00297 /****************************************************************************/
00298 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Defines