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-2016 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  if (fabs(GeomHelper::angle2D(v1, v2)) < myMinLinkAngle) {
132  check = false;
133  }
134  }
135  }
136  }
137  }
138  return check;
139 }
140 
141 
142 bool
144  bool connectable = true;
145  const PositionVector n(baseNode->getPosition(), newNode->getPosition());
146 
147  // check for range between Basenode and Newnode
148  if (connectable) {
149  SUMOReal dist = n.length();
150  if ((dist < myMinDistance) || (dist > myMaxDistance)) {
151  connectable = false;
152  }
153  }
154 
155  // check for angle restrictions
156  if (connectable) {
157  connectable = checkAngles(baseNode);
158  }
159  if (connectable) {
160  connectable = checkAngles(newNode);
161  }
162 
163  // check for intersections and range restrictions with outer links
164  if (connectable) {
165  NGEdgeList::iterator li;
166  li = myOuterLinks.begin();
167  while (connectable && (li != myOuterLinks.end())) {
168  // check intersection only if links don't share a node
169  const NGNode* const start = (*li)->getStartNode();
170  const NGNode* const end = (*li)->getEndNode();
171  const Position& p1 = start->getPosition();
172  const Position& p2 = end->getPosition();
173  if ((baseNode != start) && (baseNode != end) && (newNode != start) && (newNode != end)) {
174  connectable = !n.intersects(p1, p2);
175  }
176  // check NewNode-To-Links distance only, if NewNode isn't part of link
177  if (connectable && (newNode != start) && (newNode != end)) {
178  const SUMOReal offset = GeomHelper::nearest_offset_on_line_to_point2D(p1, p2, n[1]);
179  if (offset != GeomHelper::INVALID_OFFSET) {
180  const Position p = PositionVector(p1, p2).positionAtOffset2D(offset);
181  const SUMOReal dist = p.distanceTo2D(n[1]);
182  if (dist < myMinDistance) {
183  connectable = false;
184  }
185  }
186  }
187  ++li;
188  }
189  }
190  return connectable;
191 }
192 
193 
194 void
196  myConNodes.clear();
197  NGNodeList::iterator ni;
198  for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
199  NGNode* on = *ni;
200  if (!node->connected(on)) {
201  if ((node->getMaxNeighbours() > node->LinkList.size()) &&
202  ((on)->getMaxNeighbours() > (on)->LinkList.size())) {
203  if (canConnect(node, on)) {
204  myConNodes.push_back(on);
205  }
206  }
207  }
208  }
209 }
210 
211 
212 bool
214  // calculate position of new node based on BaseNode
216  SUMOReal angle = RandHelper::rand((SUMOReal)(2 * M_PI));
217  SUMOReal x = baseNode->getPosition().x() + dist * cos(angle);
218  SUMOReal y = baseNode->getPosition().y() + dist * sin(angle);
219  NGNode* newNode = new NGNode(myNet.getNextFreeID());
220  newNode->setX(x);
221  newNode->setY(y);
223  NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
224  if (canConnect(baseNode, newNode)) {
225  // add node
226  myNet.add(newNode);
227  myOuterNodes.push_front(newNode);
228  // add link
229  myNet.add(newLink);
230  myOuterLinks.push_back(newLink);
231  // check basenode for being outer node
232  if (baseNode->LinkList.size() >= baseNode->getMaxNeighbours()) {
233  removeOuterNode(baseNode);
234  }
235  return true;
236  } else {
237  delete newNode;
238  return false;
239  }
240 }
241 
242 
243 void
245  myNumNodes = numNodes;
246 
247  NGNode* outerNode = new NGNode(myNet.getNextFreeID());
248  outerNode->setX(0);
249  outerNode->setY(0);
250  outerNode->setMaxNeighbours(4);
251 
252  myNet.add(outerNode);
253  myOuterNodes.push_back(outerNode);
254 
255  bool created = true;
256  while ((myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
257  // brings last element to front
258  if (!created) {
259  myOuterNodes.push_front(myOuterNodes.back());
260  myOuterNodes.pop_back();
261  }
262  outerNode = myOuterNodes.back();
263  findPossibleOuterNodes(outerNode);
264  created = false;
265  if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
266  // create link
267  NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
268  if (canConnect(outerNode, myConNodes.back())) {
269  // add link
270  myNet.add(newLink);
271  myOuterLinks.push_back(newLink);
272  // check nodes for being outer node
273  if (outerNode->LinkList.size() >= outerNode->getMaxNeighbours()) {
274  removeOuterNode(outerNode);
275  }
276  if (myConNodes.back()->LinkList.size() >= myConNodes.back()->getMaxNeighbours()) {
277  removeOuterNode(myConNodes.back());
278  }
279  created = true;
280  } else {
281  delete newLink;
282  }
283  } else {
284  int count = 0;
285  do {
286  created = createNewNode(outerNode);
287  count++;
288  } while ((count <= myNumTries) && !created);
289  if (!created) {
290  outerNode->setMaxNeighbours((SUMOReal) outerNode->LinkList.size());
291  myOuterNodes.remove(outerNode);
292  }
293  }
294  }
295 }
296 
297 
298 /****************************************************************************/
299 
static SUMOReal angle2D(const Position &p1, const Position &p2)
Returns the angle between two vectors on a plane The angle is from vector 1 to vector 2...
Definition: GeomHelper.cpp:94
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.
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 nodeNo() const
Returns the number of stored nodes.
Definition: NGNet.cpp:257
int num()
Get random number of neighbours.
bool checkAngles(NGNode *node)
Checks whether the angle of this node&#39;s connections are valid.
SUMOReal getMaxNeighbours()
Returns this node&#39;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. ...
SUMOReal distanceTo2D(const Position &p2) const
returns the euclidean distance in the x-y-plane
Definition: Position.h:232
A point in 2D or 3D with translation and scaling methods.
Definition: Position.h:46
bool connected(NGNode *node) const
Returns whether the other node is connected.
Definition: NGNode.cpp:127
A list of positions.
std::string getNextFreeID()
Returns the next free id.
Definition: NGNet.cpp:74
int myNumNodes
Number of nodes to be created.
SUMOReal x() const
Returns the x-position.
Definition: Position.h:63
void setMaxNeighbours(SUMOReal value)
Sets this node&#39;s maximum neighbour number.
Definition: NGNode.h:112
The class storing the generated network.
Definition: NGNet.h:56
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.
NGEdgeList myOuterLinks
The list of outer links.
static SUMOReal nearest_offset_on_line_to_point2D(const Position &lineStart, const Position &lineEnd, const Position &p, bool perpendicular=true)
Definition: GeomHelper.cpp:100
Position positionAtOffset2D(SUMOReal pos, SUMOReal lateralOffset=0) const
Returns the position at the given length.
const Position & getPosition() const
Returns this node&#39;s position.
Definition: NGNode.h:94
#define SUMOReal
Definition: config.h:213
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.
SUMOReal y() const
Returns the y-position.
Definition: Position.h:68
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:245
static const SUMOReal INVALID_OFFSET
a value to signify offsets outside the range of [0, Line.length()]
Definition: GeomHelper.h:59
NGNet & myNet
The network to fill.