SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NGRandomNetBuilder.cpp
Go to the documentation of this file.
1 /****************************************************************************/
9 // Additional structures for building random nets
10 /****************************************************************************/
11 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
12 // Copyright (C) 2001-2013 DLR (http://www.dlr.de/) and contributors
13 /****************************************************************************/
14 //
15 // This file is part of SUMO.
16 // SUMO is free software: you can redistribute it and/or modify
17 // it under the terms of the GNU General Public License as published by
18 // the Free Software Foundation, either version 3 of the License, or
19 // (at your option) any later version.
20 //
21 /****************************************************************************/
22 
23 
24 // ===========================================================================
25 // included modules
26 // ===========================================================================
27 #ifdef _MSC_VER
28 #include <windows_config.h>
29 #else
30 #include <config.h>
31 #endif
32 
33 #include <iostream>
34 #include <math.h>
35 #include <stdlib.h>
36 #include "NGRandomNetBuilder.h"
37 #include <utils/geom/GeomHelper.h>
39 
40 #ifdef CHECK_MEMORY_LEAKS
41 #include <foreign/nvwa/debug_new.h>
42 #endif // CHECK_MEMORY_LEAKS
43 
44 
45 // ===========================================================================
46 // method definitions
47 // ===========================================================================
48 // ---------------------------------------------------------------------------
49 // TNeighbourDistribution-definitions
50 // ---------------------------------------------------------------------------
51 void
52 TNeighbourDistribution::add(int NumNeighbours, SUMOReal ratio) {
53  myNeighbours[NumNeighbours] = ratio;
54 }
55 
56 
57 int
59  SUMOReal sum = 0, RandValue;
60  std::map<int, SUMOReal>::iterator i;
61  // total sum of ratios
62  for (i = myNeighbours.begin(); i != myNeighbours.end(); ++i) {
63  sum += (*i).second;
64  }
65  // RandValue = [0,sum]
66  RandValue = RandHelper::rand(sum);
67  // find selected item
68  i = myNeighbours.begin();
69  sum = (*i).second;
70  while ((i != myNeighbours.end()) && (sum < RandValue)) {
71  ++i;
72  sum += (*i).second;
73  }
74  return (*i).first;
75 }
76 
77 
78 // ---------------------------------------------------------------------------
79 // NGRandomNetBuilder-definitions
80 // ---------------------------------------------------------------------------
82  SUMOReal maxDistance, SUMOReal connectivity,
83  int numTries, const TNeighbourDistribution& neighborDist)
84  : myNet(net), myMinLinkAngle(minAngle), myMinDistance(minDistance),
85  myMaxDistance(maxDistance), myConnectivity(connectivity), myNumTries(numTries),
86  myNeighbourDistribution(neighborDist) {
87 }
88 
89 
90 void
92  for (NGNodeList::iterator ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
93  if (*ni == node) {
94  myOuterNodes.erase(ni);
95  return;
96  }
97  }
98 }
99 
100 
101 bool
103  bool check = true;
104 
105  if (node->LinkList.size() > 1) {
106  // loop over all links
107  NGEdgeList::iterator li;
108  NGNode* ni;
109  for (li = node->LinkList.begin(); li != node->LinkList.end(); ++li) {
110  // calc vector of currentnode
111  if ((*li)->getStartNode() == node) {
112  ni = (*li)->getEndNode();
113  } else {
114  ni = (*li)->getStartNode();
115  }
116  Position v1(
117  ni->getPosition().x() - node->getPosition().x(),
118  ni->getPosition().y() - node->getPosition().y());
119  // loop over all links
120  NGEdgeList::iterator lj;
121  for (lj = node->LinkList.begin(); lj != node->LinkList.end(); ++lj) {
122  if (li != lj) {
123  if ((*lj)->getStartNode() == node) {
124  ni = (*lj)->getEndNode();
125  } else {
126  ni = (*lj)->getStartNode();
127  }
128  Position v2(
129  ni->getPosition().x() - node->getPosition().x(),
130  ni->getPosition().y() - node->getPosition().y());
131  SUMOReal angle = GeomHelper::Angle2D(v1.x(), v1.y(), v2.x(), v2.y());
132  if (fabs((SUMOReal) angle) < myMinLinkAngle) {
133  check = false;
134  }
135  }
136  }
137  }
138  }
139  return check;
140 }
141 
142 
143 bool
145  bool connectable = true;
146  Position n1(baseNode->getPosition());
147  Position n2(newNode->getPosition());
148 
149  // check for range between Basenode and Newnode
150  if (connectable) {
151  SUMOReal dist = n1.distanceTo(n2);
152  if ((dist < myMinDistance) || (dist > myMaxDistance)) {
153  connectable = false;
154  }
155  }
156 
157  // check for angle restrictions
158  if (connectable) {
159  connectable = checkAngles(baseNode);
160  }
161  if (connectable) {
162  connectable = checkAngles(newNode);
163  }
164 
165  // check for intersections and range restrictions with outer links
166  if (connectable) {
167  NGEdgeList::iterator li;
168  li = myOuterLinks.begin();
169  while ((connectable == true) && (li != myOuterLinks.end())) {
170  // check intersection only if links don't share a node
171  Position p1((*li)->getStartNode()->getPosition());
172  Position p2((*li)->getEndNode()->getPosition());
173  if ((baseNode != (*li)->getStartNode()) && (baseNode != (*li)->getEndNode())
174  && (newNode != (*li)->getStartNode()) && (newNode != (*li)->getEndNode())) {
175  connectable = !GeomHelper::intersects(n1, n2, p1, p2);
176 
177  }
178  // check NewNode-To-Links distance only, if NewNode isn't part of link
179  if ((connectable) &&
180  (newNode != (*li)->getStartNode()) && (newNode != (*li)->getEndNode())) {
181  SUMOReal dist = GeomHelper::distancePointLine(n2, p1, p2);
182  if ((dist < myMinDistance) && (dist > -1)) {
183  connectable = false;
184  }
185  }
186  ++li;
187  }
188  }
189  return connectable;
190 }
191 
192 
193 void
195  myConNodes.clear();
196  NGNodeList::iterator ni;
197  for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
198  NGNode* on = *ni;
199  if (!node->connected(on)) {
200  if ((node->getMaxNeighbours() > node->LinkList.size()) &&
201  ((on)->getMaxNeighbours() > (on)->LinkList.size())) {
202  if (canConnect(node, on)) {
203  myConNodes.push_back(on);
204  }
205  }
206  }
207  }
208 }
209 
210 
211 bool
213  // calculate position of new node based on BaseNode
215  SUMOReal angle = RandHelper::rand((SUMOReal)(2 * PI));
216  SUMOReal x = baseNode->getPosition().x() + dist * cos(angle);
217  SUMOReal y = baseNode->getPosition().y() + dist * sin(angle);
218  NGNode* newNode = new NGNode(myNet.getNextFreeID());
219  newNode->setX(x);
220  newNode->setY(y);
222  NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
223  if (canConnect(baseNode, newNode)) {
224  // add node
225  myNet.add(newNode);
226  myOuterNodes.push_front(newNode);
227  // add link
228  myNet.add(newLink);
229  myOuterLinks.push_back(newLink);
230  // check basenode for being outer node
231  if (baseNode->LinkList.size() >= baseNode->getMaxNeighbours()) {
232  removeOuterNode(baseNode);
233  }
234  return true;
235  } else {
236  delete newNode;
237  return false;
238  }
239 }
240 
241 
242 void
244  myNumNodes = numNodes;
245 
246  NGNode* outerNode = new NGNode(myNet.getNextFreeID());
247  outerNode->setX(0);
248  outerNode->setY(0);
249  outerNode->setMaxNeighbours(4);
250 
251  myNet.add(outerNode);
252  myOuterNodes.push_back(outerNode);
253 
254  bool created = true;
255  while (((int) myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
256  // brings last element to front
257  if (!created) {
258  myOuterNodes.push_front(myOuterNodes.back());
259  myOuterNodes.pop_back();
260  }
261  outerNode = myOuterNodes.back();
262  findPossibleOuterNodes(outerNode);
263  created = false;
264  if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
265  // create link
266  NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
267  if (canConnect(outerNode, myConNodes.back())) {
268  // add link
269  myNet.add(newLink);
270  myOuterLinks.push_back(newLink);
271  // check nodes for being outer node
272  if (outerNode->LinkList.size() >= outerNode->getMaxNeighbours()) {
273  removeOuterNode(outerNode);
274  }
275  if (myConNodes.back()->LinkList.size() >= myConNodes.back()->getMaxNeighbours()) {
276  removeOuterNode(myConNodes.back());
277  }
278  created = true;
279  } else {
280  delete newLink;
281  }
282  } else {
283  int count = 0;
284  do {
285  created = createNewNode(outerNode);
286  count++;
287  } while ((count <= myNumTries) && !created);
288  if (!created) {
289  outerNode->setMaxNeighbours((SUMOReal) outerNode->LinkList.size());
290  myOuterNodes.remove(outerNode);
291  }
292  }
293  }
294 }
295 
296 
297 /****************************************************************************/
298