SUMO - Simulation of Urban MObility
NGRandomNetBuilder.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-2017 German Aerospace Center (DLR) and others.
4 /****************************************************************************/
5 //
6 // This program and the accompanying materials
7 // are made available under the terms of the Eclipse Public License v2.0
8 // which accompanies this distribution, and is available at
9 // http://www.eclipse.org/legal/epl-v20.html
10 //
11 /****************************************************************************/
19 // Additional structures for building random nets
20 /****************************************************************************/
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #ifdef _MSC_VER
27 #include <windows_config.h>
28 #else
29 #include <config.h>
30 #endif
31 
32 #include <iostream>
33 #include <cmath>
34 #include <stdlib.h>
35 #include "NGRandomNetBuilder.h"
36 #include <utils/geom/GeomHelper.h>
38 
39 
40 // ===========================================================================
41 // method definitions
42 // ===========================================================================
43 // ---------------------------------------------------------------------------
44 // NGRandomNetBuilder-definitions
45 // ---------------------------------------------------------------------------
46 NGRandomNetBuilder::NGRandomNetBuilder(NGNet& net, double minAngle, double minDistance,
47  double maxDistance, double connectivity,
48  int numTries, const RandomDistributor<int>& neighborDist)
49  : myNet(net), myMinLinkAngle(minAngle), myMinDistance(minDistance),
50  myMaxDistance(maxDistance), myConnectivity(connectivity), myNumTries(numTries),
51  myNeighbourDistribution(neighborDist) {
52 }
53 
54 
55 void
57  for (NGNodeList::iterator ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
58  if (*ni == node) {
59  myOuterNodes.erase(ni);
60  return;
61  }
62  }
63 }
64 
65 
66 bool
68  bool check = true;
69 
70  if (node->LinkList.size() > 1) {
71  // loop over all links
72  NGEdgeList::iterator li;
73  NGNode* ni;
74  for (li = node->LinkList.begin(); li != node->LinkList.end(); ++li) {
75  // calc vector of currentnode
76  if ((*li)->getStartNode() == node) {
77  ni = (*li)->getEndNode();
78  } else {
79  ni = (*li)->getStartNode();
80  }
81  Position v1(
82  ni->getPosition().x() - node->getPosition().x(),
83  ni->getPosition().y() - node->getPosition().y());
84  // loop over all links
85  NGEdgeList::iterator lj;
86  for (lj = node->LinkList.begin(); lj != node->LinkList.end(); ++lj) {
87  if (li != lj) {
88  if ((*lj)->getStartNode() == node) {
89  ni = (*lj)->getEndNode();
90  } else {
91  ni = (*lj)->getStartNode();
92  }
93  Position v2(
94  ni->getPosition().x() - node->getPosition().x(),
95  ni->getPosition().y() - node->getPosition().y());
96  if (fabs(GeomHelper::angle2D(v1, v2)) < myMinLinkAngle) {
97  check = false;
98  }
99  }
100  }
101  }
102  }
103  return check;
104 }
105 
106 
107 bool
109  bool connectable = true;
110  const PositionVector n(baseNode->getPosition(), newNode->getPosition());
111 
112  // check for range between Basenode and Newnode
113  if (connectable) {
114  double dist = n.length();
115  if ((dist < myMinDistance) || (dist > myMaxDistance)) {
116  connectable = false;
117  }
118  }
119 
120  // check for angle restrictions
121  if (connectable) {
122  connectable = checkAngles(baseNode);
123  }
124  if (connectable) {
125  connectable = checkAngles(newNode);
126  }
127 
128  // check for intersections and range restrictions with outer links
129  if (connectable) {
130  NGEdgeList::iterator li;
131  li = myOuterLinks.begin();
132  while (connectable && (li != myOuterLinks.end())) {
133  // check intersection only if links don't share a node
134  const NGNode* const start = (*li)->getStartNode();
135  const NGNode* const end = (*li)->getEndNode();
136  const Position& p1 = start->getPosition();
137  const Position& p2 = end->getPosition();
138  if ((baseNode != start) && (baseNode != end) && (newNode != start) && (newNode != end)) {
139  connectable = !n.intersects(p1, p2);
140  }
141  // check NewNode-To-Links distance only, if NewNode isn't part of link
142  if (connectable && (newNode != start) && (newNode != end)) {
143  const double offset = GeomHelper::nearest_offset_on_line_to_point2D(p1, p2, n[1]);
144  if (offset != GeomHelper::INVALID_OFFSET) {
145  const Position p = PositionVector(p1, p2).positionAtOffset2D(offset);
146  const double dist = p.distanceTo2D(n[1]);
147  if (dist < myMinDistance) {
148  connectable = false;
149  }
150  }
151  }
152  ++li;
153  }
154  }
155  return connectable;
156 }
157 
158 
159 void
161  myConNodes.clear();
162  NGNodeList::iterator ni;
163  for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
164  NGNode* on = *ni;
165  if (!node->connected(on)) {
166  if ((node->getMaxNeighbours() > (int)node->LinkList.size()) &&
167  (on->getMaxNeighbours() > (int)on->LinkList.size())) {
168  if (canConnect(node, on)) {
169  myConNodes.push_back(on);
170  }
171  }
172  }
173  }
174 }
175 
176 
177 bool
179  // calculate position of new node based on BaseNode
181  double angle = RandHelper::rand((double)(2 * M_PI));
182  double x = baseNode->getPosition().x() + dist * cos(angle);
183  double y = baseNode->getPosition().y() + dist * sin(angle);
184  NGNode* newNode = new NGNode(myNet.getNextFreeID());
185  newNode->setX(x);
186  newNode->setY(y);
188  NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
189  if (canConnect(baseNode, newNode)) {
190  // add node
191  myNet.add(newNode);
192  myOuterNodes.push_front(newNode);
193  // add link
194  myNet.add(newLink);
195  myOuterLinks.push_back(newLink);
196  // check basenode for being outer node
197  if ((int)baseNode->LinkList.size() >= baseNode->getMaxNeighbours()) {
198  removeOuterNode(baseNode);
199  }
200  return true;
201  } else {
202  delete newNode;
203  return false;
204  }
205 }
206 
207 
208 void
210  myNumNodes = numNodes;
211 
212  NGNode* outerNode = new NGNode(myNet.getNextFreeID());
213  outerNode->setX(0);
214  outerNode->setY(0);
215  outerNode->setMaxNeighbours(4);
216 
217  myNet.add(outerNode);
218  myOuterNodes.push_back(outerNode);
219 
220  bool created = true;
221  while ((myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
222  // brings last element to front
223  if (!created) {
224  myOuterNodes.push_front(myOuterNodes.back());
225  myOuterNodes.pop_back();
226  }
227  outerNode = myOuterNodes.back();
228  findPossibleOuterNodes(outerNode);
229  created = false;
230  if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
231  // create link
232  NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
233  if (canConnect(outerNode, myConNodes.back())) {
234  // add link
235  myNet.add(newLink);
236  myOuterLinks.push_back(newLink);
237  // check nodes for being outer node
238  if ((int)outerNode->LinkList.size() >= outerNode->getMaxNeighbours()) {
239  removeOuterNode(outerNode);
240  }
241  if ((int)myConNodes.back()->LinkList.size() >= myConNodes.back()->getMaxNeighbours()) {
242  removeOuterNode(myConNodes.back());
243  }
244  created = true;
245  } else {
246  delete newLink;
247  }
248  } else {
249  int count = 0;
250  do {
251  created = createNewNode(outerNode);
252  count++;
253  } while ((count <= myNumTries) && !created);
254  if (!created) {
255  outerNode->setMaxNeighbours((int)outerNode->LinkList.size());
256  myOuterNodes.remove(outerNode);
257  }
258  }
259  }
260 }
261 
262 
263 /****************************************************************************/
264 
A netgen-representation of an edge.
Definition: NGEdge.h:61
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:249
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:67
double myMinDistance
Minimum distance allowed between two nodes.
double myConnectivity
Probability of connecting to a existing node if possible.
static double rand(std::mt19937 *rng=0)
Returns a random real number in [0, 1)
Definition: RandHelper.h:64
double x() const
Returns the x-position.
Definition: Position.h:62
int nodeNo() const
Returns the number of stored nodes.
Definition: NGNet.cpp:252
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:95
void setX(double x)
Sets a new value for x-position.
Definition: NGNode.h:120
T get(std::mt19937 *which=0) const
Draw a sample of the distribution.
A point in 2D or 3D with translation and scaling methods.
Definition: Position.h:45
bool connected(NGNode *node) const
Returns whether the other node is connected.
Definition: NGNode.cpp:122
A list of positions.
std::string getNextFreeID()
Returns the next free id.
Definition: NGNet.cpp:69
int getMaxNeighbours()
Returns this node&#39;s maximum neighbour number.
Definition: NGNode.h:102
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:89
int myNumNodes
Number of nodes to be created.
The class storing the generated network.
Definition: NGNet.h:55
static const double INVALID_OFFSET
a value to signify offsets outside the range of [0, Line.length()]
Definition: GeomHelper.h:58
void removeOuterNode(NGNode *node)
Removes the given node from the list of outer nodes.
double length() const
Returns the length.
#define M_PI
Definition: odrSpiral.cpp:40
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:111
const Position & getPosition() const
Returns this node&#39;s position.
Definition: NGNode.h:93
double myMaxDistance
Maximum distance allowed between two nodes.
A netgen-representation of a node.
Definition: NGNode.h:57
void setY(double y)
Sets a new value for y-position.
Definition: NGNode.h:129
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:197
void add(NGNode *node)
Adds the given node to the network.
Definition: NGNet.cpp:240
NGNet & myNet
The network to fill.