SUMO - Simulation of Urban MObility
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.dlr.de/
12 // Copyright (C) 2001-2015 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 * M_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 
static SUMOReal Angle2D(SUMOReal x1, SUMOReal y1, SUMOReal x2, SUMOReal y2)
Definition: GeomHelper.cpp:224
void setX(SUMOReal x)
Sets a new value for x-position.
Definition: NGNode.h:121
void add(int numNeighbours, SUMOReal ratio)
adds a neighbour item to list
A netgen-representation of an edge.
Definition: NGEdge.h:62
NGNodeList myOuterNodes
The list of outer nodes.
void findPossibleOuterNodes(NGNode *node)
finds possible connections between Node and OuterNodes complying with restrictions ...
#define M_PI
Definition: angles.h:37
void createNet(int numNodes)
Builds a NGNet using the set values.
bool connected(NGNode *node) const
Returns whether the other node is connected.
Definition: NGNode.cpp:127
TNeighbourDistribution myNeighbourDistribution
The distrubtion of number of neighbours.
SUMOReal myConnectivity
Probability of connecting to a existing node if possible.
SUMOReal myMaxDistance
Maximum distance allowed between two nodes.
static SUMOReal rand()
Returns a random real number in [0, 1)
Definition: RandHelper.h:62
int num()
Get random number of neighbours.
bool checkAngles(NGNode *node)
Checks whether the angle of this node's connections are valid.
SUMOReal x() const
Returns the x-position.
Definition: Position.h:63
SUMOReal getMaxNeighbours()
Returns this node's maximum neighbour number.
Definition: NGNode.h:103
bool canConnect(NGNode *baseNode, NGNode *newNode)
Checks whether connecting the given two nodes complies with the set restrictions. ...
size_t nodeNo() const
Returns the number of stored nodes.
Definition: NGNet.cpp:254
static bool intersects(const Position &p11, const Position &p12, const Position &p21, const Position &p22)
return whether given lines intersect
Definition: GeomHelper.cpp:145
A point in 2D or 3D with translation and scaling methods.
Definition: Position.h:46
std::string getNextFreeID()
Returns the next free id.
Definition: NGNet.cpp:74
static SUMOReal distancePointLine(const Position &point, const Position &lineStart, const Position &lineEnd)
Definition: GeomHelper.cpp:288
int myNumNodes
Number of nodes to be created.
void setMaxNeighbours(SUMOReal value)
Sets this node's maximum neighbour number.
Definition: NGNode.h:112
The class storing the generated network.
Definition: NGNet.h:56
const Position & getPosition() const
Returns this node's position.
Definition: NGNode.h:94
std::map< int, SUMOReal > myNeighbours
A map from neighbor number to their probabilities.
void removeOuterNode(NGNode *node)
Removes the given node from the list of outer nodes.
SUMOReal y() const
Returns the y-position.
Definition: Position.h:68
NGEdgeList myOuterLinks
The list of outer links.
#define SUMOReal
Definition: config.h:218
SUMOReal myMinDistance
Minimum distance allowed between two nodes.
void setY(SUMOReal y)
Sets a new value for y-position.
Definition: NGNode.h:130
SUMOReal myMinLinkAngle
Minimum angle allowed between two links.
A netgen-representation of a node.
Definition: NGNode.h:58
bool createNewNode(NGNode *baseNode)
Creates new random node.
NGRandomNetBuilder(NGNet &net, SUMOReal minAngle, SUMOReal minDistance, SUMOReal maxDistance, SUMOReal connectivity, int numTries, const TNeighbourDistribution &neighborDist)
Constructor.
int myNumTries
Number of tries to create a new node.
NGEdgeList LinkList
List of connected links.
Definition: NGNode.h:198
void add(NGNode *node)
Adds the given node to the network.
Definition: NGNet.cpp:242
NGNet & myNet
The network to fill.