SUMO - Simulation of Urban MObility
|
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