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-2017 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 
41 // ===========================================================================
42 // method definitions
43 // ===========================================================================
44 // ---------------------------------------------------------------------------
45 // NGRandomNetBuilder-definitions
46 // ---------------------------------------------------------------------------
47 NGRandomNetBuilder::NGRandomNetBuilder(NGNet& net, double minAngle, double minDistance,
48  double maxDistance, double connectivity,
49  int numTries, const RandomDistributor<int>& neighborDist)
50  : myNet(net), myMinLinkAngle(minAngle), myMinDistance(minDistance),
51  myMaxDistance(maxDistance), myConnectivity(connectivity), myNumTries(numTries),
52  myNeighbourDistribution(neighborDist) {
53 }
54 
55 
56 void
58  for (NGNodeList::iterator ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
59  if (*ni == node) {
60  myOuterNodes.erase(ni);
61  return;
62  }
63  }
64 }
65 
66 
67 bool
69  bool check = true;
70 
71  if (node->LinkList.size() > 1) {
72  // loop over all links
73  NGEdgeList::iterator li;
74  NGNode* ni;
75  for (li = node->LinkList.begin(); li != node->LinkList.end(); ++li) {
76  // calc vector of currentnode
77  if ((*li)->getStartNode() == node) {
78  ni = (*li)->getEndNode();
79  } else {
80  ni = (*li)->getStartNode();
81  }
82  Position v1(
83  ni->getPosition().x() - node->getPosition().x(),
84  ni->getPosition().y() - node->getPosition().y());
85  // loop over all links
86  NGEdgeList::iterator lj;
87  for (lj = node->LinkList.begin(); lj != node->LinkList.end(); ++lj) {
88  if (li != lj) {
89  if ((*lj)->getStartNode() == node) {
90  ni = (*lj)->getEndNode();
91  } else {
92  ni = (*lj)->getStartNode();
93  }
94  Position v2(
95  ni->getPosition().x() - node->getPosition().x(),
96  ni->getPosition().y() - node->getPosition().y());
97  if (fabs(GeomHelper::angle2D(v1, v2)) < myMinLinkAngle) {
98  check = false;
99  }
100  }
101  }
102  }
103  }
104  return check;
105 }
106 
107 
108 bool
110  bool connectable = true;
111  const PositionVector n(baseNode->getPosition(), newNode->getPosition());
112 
113  // check for range between Basenode and Newnode
114  if (connectable) {
115  double dist = n.length();
116  if ((dist < myMinDistance) || (dist > myMaxDistance)) {
117  connectable = false;
118  }
119  }
120 
121  // check for angle restrictions
122  if (connectable) {
123  connectable = checkAngles(baseNode);
124  }
125  if (connectable) {
126  connectable = checkAngles(newNode);
127  }
128 
129  // check for intersections and range restrictions with outer links
130  if (connectable) {
131  NGEdgeList::iterator li;
132  li = myOuterLinks.begin();
133  while (connectable && (li != myOuterLinks.end())) {
134  // check intersection only if links don't share a node
135  const NGNode* const start = (*li)->getStartNode();
136  const NGNode* const end = (*li)->getEndNode();
137  const Position& p1 = start->getPosition();
138  const Position& p2 = end->getPosition();
139  if ((baseNode != start) && (baseNode != end) && (newNode != start) && (newNode != end)) {
140  connectable = !n.intersects(p1, p2);
141  }
142  // check NewNode-To-Links distance only, if NewNode isn't part of link
143  if (connectable && (newNode != start) && (newNode != end)) {
144  const double offset = GeomHelper::nearest_offset_on_line_to_point2D(p1, p2, n[1]);
145  if (offset != GeomHelper::INVALID_OFFSET) {
146  const Position p = PositionVector(p1, p2).positionAtOffset2D(offset);
147  const double dist = p.distanceTo2D(n[1]);
148  if (dist < myMinDistance) {
149  connectable = false;
150  }
151  }
152  }
153  ++li;
154  }
155  }
156  return connectable;
157 }
158 
159 
160 void
162  myConNodes.clear();
163  NGNodeList::iterator ni;
164  for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
165  NGNode* on = *ni;
166  if (!node->connected(on)) {
167  if ((node->getMaxNeighbours() > (int)node->LinkList.size()) &&
168  (on->getMaxNeighbours() > (int)on->LinkList.size())) {
169  if (canConnect(node, on)) {
170  myConNodes.push_back(on);
171  }
172  }
173  }
174  }
175 }
176 
177 
178 bool
180  // calculate position of new node based on BaseNode
182  double angle = RandHelper::rand((double)(2 * M_PI));
183  double x = baseNode->getPosition().x() + dist * cos(angle);
184  double y = baseNode->getPosition().y() + dist * sin(angle);
185  NGNode* newNode = new NGNode(myNet.getNextFreeID());
186  newNode->setX(x);
187  newNode->setY(y);
189  NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
190  if (canConnect(baseNode, newNode)) {
191  // add node
192  myNet.add(newNode);
193  myOuterNodes.push_front(newNode);
194  // add link
195  myNet.add(newLink);
196  myOuterLinks.push_back(newLink);
197  // check basenode for being outer node
198  if ((int)baseNode->LinkList.size() >= baseNode->getMaxNeighbours()) {
199  removeOuterNode(baseNode);
200  }
201  return true;
202  } else {
203  delete newNode;
204  return false;
205  }
206 }
207 
208 
209 void
211  myNumNodes = numNodes;
212 
213  NGNode* outerNode = new NGNode(myNet.getNextFreeID());
214  outerNode->setX(0);
215  outerNode->setY(0);
216  outerNode->setMaxNeighbours(4);
217 
218  myNet.add(outerNode);
219  myOuterNodes.push_back(outerNode);
220 
221  bool created = true;
222  while ((myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
223  // brings last element to front
224  if (!created) {
225  myOuterNodes.push_front(myOuterNodes.back());
226  myOuterNodes.pop_back();
227  }
228  outerNode = myOuterNodes.back();
229  findPossibleOuterNodes(outerNode);
230  created = false;
231  if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
232  // create link
233  NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
234  if (canConnect(outerNode, myConNodes.back())) {
235  // add link
236  myNet.add(newLink);
237  myOuterLinks.push_back(newLink);
238  // check nodes for being outer node
239  if ((int)outerNode->LinkList.size() >= outerNode->getMaxNeighbours()) {
240  removeOuterNode(outerNode);
241  }
242  if ((int)myConNodes.back()->LinkList.size() >= myConNodes.back()->getMaxNeighbours()) {
243  removeOuterNode(myConNodes.back());
244  }
245  created = true;
246  } else {
247  delete newLink;
248  }
249  } else {
250  int count = 0;
251  do {
252  created = createNewNode(outerNode);
253  count++;
254  } while ((count <= myNumTries) && !created);
255  if (!created) {
256  outerNode->setMaxNeighbours((int)outerNode->LinkList.size());
257  myOuterNodes.remove(outerNode);
258  }
259  }
260  }
261 }
262 
263 
264 /****************************************************************************/
265 
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 ...
double distanceTo2D(const Position &p2) const
returns the euclidean distance in the x-y-plane
Definition: Position.h:250
#define M_PI
Definition: angles.h:37
void createNet(int numNodes)
Builds a NGNet using the set values.
double myMinLinkAngle
Minimum angle allowed between two links.
Position positionAtOffset2D(double pos, double lateralOffset=0) const
Returns the position at the given length.
double y() const
Returns the y-position.
Definition: Position.h:68
double myMinDistance
Minimum distance allowed between two nodes.
double myConnectivity
Probability of connecting to a existing node if possible.
double x() const
Returns the x-position.
Definition: Position.h:63
int nodeNo() const
Returns the number of stored nodes.
Definition: NGNet.cpp:253
bool checkAngles(NGNode *node)
Checks whether the angle of this node&#39;s connections are valid.
bool canConnect(NGNode *baseNode, NGNode *newNode)
Checks whether connecting the given two nodes complies with the set restrictions. ...
static double nearest_offset_on_line_to_point2D(const Position &lineStart, const Position &lineEnd, const Position &p, bool perpendicular=true)
Definition: GeomHelper.cpp:96
void setX(double x)
Sets a new value for x-position.
Definition: NGNode.h:121
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:123
A list of positions.
std::string getNextFreeID()
Returns the next free id.
Definition: NGNet.cpp:70
int getMaxNeighbours()
Returns this node&#39;s maximum neighbour number.
Definition: NGNode.h:103
static double 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:90
int myNumNodes
Number of nodes to be created.
static double rand()
Returns a random real number in [0, 1)
Definition: RandHelper.h:62
The class storing the generated network.
Definition: NGNet.h:56
static const double INVALID_OFFSET
a value to signify offsets outside the range of [0, Line.length()]
Definition: GeomHelper.h:59
T get(MTRand *which=0) const
Draw a sample of the distribution.
void removeOuterNode(NGNode *node)
Removes the given node from the list of outer nodes.
double length() const
Returns the length.
NGEdgeList myOuterLinks
The list of outer links.
NGRandomNetBuilder(NGNet &net, double minAngle, double minDistance, double maxDistance, double connectivity, int numTries, const RandomDistributor< int > &neighborDist)
Constructor.
void setMaxNeighbours(int value)
Sets this node&#39;s maximum neighbour number.
Definition: NGNode.h:112
const Position & getPosition() const
Returns this node&#39;s position.
Definition: NGNode.h:94
double myMaxDistance
Maximum distance allowed between two nodes.
A netgen-representation of a node.
Definition: NGNode.h:58
void setY(double y)
Sets a new value for y-position.
Definition: NGNode.h:130
bool createNewNode(NGNode *baseNode)
Creates new random node.
int myNumTries
Number of tries to create a new node.
RandomDistributor< int > myNeighbourDistribution
The distribution of number of neighbours.
NGEdgeList LinkList
List of connected links.
Definition: NGNode.h:198
void add(NGNode *node)
Adds the given node to the network.
Definition: NGNet.cpp:241
NGNet & myNet
The network to fill.