Eclipse 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-2019 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
17 // Additional structures for building random nets
18 /****************************************************************************/
19 
20 
21 // ===========================================================================
22 // included modules
23 // ===========================================================================
24 #include <config.h>
25 
26 #include <iostream>
27 #include <cmath>
28 #include <stdlib.h>
29 #include "NGRandomNetBuilder.h"
30 #include <utils/geom/GeomHelper.h>
31 #include <utils/common/StdDefs.h>
33 
34 
35 // ===========================================================================
36 // method definitions
37 // ===========================================================================
38 // ---------------------------------------------------------------------------
39 // NGRandomNetBuilder-definitions
40 // ---------------------------------------------------------------------------
41 NGRandomNetBuilder::NGRandomNetBuilder(NGNet& net, double minAngle, double minDistance,
42  double maxDistance, double connectivity,
43  int numTries, const RandomDistributor<int>& neighborDist)
44  : myNet(net), myMinLinkAngle(minAngle), myMinDistance(minDistance),
45  myMaxDistance(maxDistance), myConnectivity(connectivity), myNumTries(numTries),
46  myNeighbourDistribution(neighborDist) {
47 }
48 
49 
50 void
52  for (NGNodeList::iterator ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
53  if (*ni == node) {
54  myOuterNodes.erase(ni);
55  return;
56  }
57  }
58 }
59 
60 
61 bool
63  bool check = true;
64 
65  if (node->LinkList.size() > 1) {
66  // loop over all links
67  NGEdgeList::iterator li;
68  NGNode* ni;
69  for (li = node->LinkList.begin(); li != node->LinkList.end(); ++li) {
70  // calc vector of currentnode
71  if ((*li)->getStartNode() == node) {
72  ni = (*li)->getEndNode();
73  } else {
74  ni = (*li)->getStartNode();
75  }
76  Position v1(
77  ni->getPosition().x() - node->getPosition().x(),
78  ni->getPosition().y() - node->getPosition().y());
79  // loop over all links
80  NGEdgeList::iterator lj;
81  for (lj = node->LinkList.begin(); lj != node->LinkList.end(); ++lj) {
82  if (li != lj) {
83  if ((*lj)->getStartNode() == node) {
84  ni = (*lj)->getEndNode();
85  } else {
86  ni = (*lj)->getStartNode();
87  }
88  Position v2(
89  ni->getPosition().x() - node->getPosition().x(),
90  ni->getPosition().y() - node->getPosition().y());
91  if (fabs(GeomHelper::angle2D(v1, v2)) < myMinLinkAngle) {
92  check = false;
93  }
94  }
95  }
96  }
97  }
98  return check;
99 }
100 
101 
102 bool
104  bool connectable = true;
105  const PositionVector n(baseNode->getPosition(), newNode->getPosition());
106 
107  // check for range between Basenode and Newnode
108  if (connectable) {
109  double dist = n.length();
110  if ((dist < myMinDistance) || (dist > myMaxDistance)) {
111  connectable = false;
112  }
113  }
114 
115  // check for angle restrictions
116  if (connectable) {
117  connectable = checkAngles(baseNode);
118  }
119  if (connectable) {
120  connectable = checkAngles(newNode);
121  }
122 
123  // check for intersections and range restrictions with outer links
124  if (connectable) {
125  NGEdgeList::iterator li;
126  li = myOuterLinks.begin();
127  while (connectable && (li != myOuterLinks.end())) {
128  // check intersection only if links don't share a node
129  const NGNode* const start = (*li)->getStartNode();
130  const NGNode* const end = (*li)->getEndNode();
131  const Position& p1 = start->getPosition();
132  const Position& p2 = end->getPosition();
133  if ((baseNode != start) && (baseNode != end) && (newNode != start) && (newNode != end)) {
134  connectable = !n.intersects(p1, p2);
135  }
136  // check NewNode-To-Links distance only, if NewNode isn't part of link
137  if (connectable && (newNode != start) && (newNode != end)) {
138  const double offset = GeomHelper::nearest_offset_on_line_to_point2D(p1, p2, n[1]);
139  if (offset != GeomHelper::INVALID_OFFSET) {
140  const Position p = PositionVector(p1, p2).positionAtOffset2D(offset);
141  const double dist = p.distanceTo2D(n[1]);
142  if (dist < myMinDistance) {
143  connectable = false;
144  }
145  }
146  }
147  ++li;
148  }
149  }
150  return connectable;
151 }
152 
153 
154 void
156  myConNodes.clear();
157  NGNodeList::iterator ni;
158  for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
159  NGNode* on = *ni;
160  if (!node->connected(on)) {
161  if ((node->getMaxNeighbours() > (int)node->LinkList.size()) &&
162  (on->getMaxNeighbours() > (int)on->LinkList.size())) {
163  if (canConnect(node, on)) {
164  myConNodes.push_back(on);
165  }
166  }
167  }
168  }
169 }
170 
171 
172 bool
173 NGRandomNetBuilder::createNewNode(NGNode* baseNode, bool gridMode) {
174  // calculate position of new node based on BaseNode
176  double angle = RandHelper::rand((double)(2 * M_PI));
177  if (gridMode) {
178  // dist must be a multiple of minDist
179  dist = MAX2(1, int(dist / myMinDistance)) * myMinDistance;
180  // angle must be a multiple of 90 degrees
181  angle = RandHelper::rand(4) * 0.5 * M_PI;
182  }
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
210 NGRandomNetBuilder::createNet(int numNodes, bool gridMode) {
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, gridMode);
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 
NGRandomNetBuilder::myConNodes
NGNodeList myConNodes
Definition: NGRandomNetBuilder.h:126
NGRandomNetBuilder::myNet
NGNet & myNet
The network to fill.
Definition: NGRandomNetBuilder.h:117
NGRandomNetBuilder::myNeighbourDistribution
RandomDistributor< int > myNeighbourDistribution
The distribution of number of neighbours.
Definition: NGRandomNetBuilder.h:153
NGNode::LinkList
NGEdgeList LinkList
List of connected links.
Definition: NGNode.h:191
NGRandomNetBuilder::myConnectivity
double myConnectivity
Probability of connecting to a existing node if possible.
Definition: NGRandomNetBuilder.h:142
NGNet::getNextFreeID
std::string getNextFreeID()
Returns the next free id.
Definition: NGNet.cpp:66
NGRandomNetBuilder::findPossibleOuterNodes
void findPossibleOuterNodes(NGNode *node)
finds possible connections between Node and OuterNodes complying with restrictions
Definition: NGRandomNetBuilder.cpp:155
NGRandomNetBuilder::canConnect
bool canConnect(NGNode *baseNode, NGNode *newNode)
Checks whether connecting the given two nodes complies with the set restrictions.
Definition: NGRandomNetBuilder.cpp:103
NGEdge
A netgen-representation of an edge.
Definition: NGEdge.h:55
NGRandomNetBuilder::myMinLinkAngle
double myMinLinkAngle
Minimum angle allowed between two links.
Definition: NGRandomNetBuilder.h:133
NGRandomNetBuilder::myMinDistance
double myMinDistance
Minimum distance allowed between two nodes.
Definition: NGRandomNetBuilder.h:136
NGNode::connected
bool connected(NGNode *node) const
Returns whether the other node is connected.
Definition: NGNode.cpp:116
PositionVector::length
double length() const
Returns the length.
Definition: PositionVector.cpp:476
GeomHelper::nearest_offset_on_line_to_point2D
static double nearest_offset_on_line_to_point2D(const Position &lineStart, const Position &lineEnd, const Position &p, bool perpendicular=true)
Definition: GeomHelper.cpp:90
PositionVector
A list of positions.
Definition: PositionVector.h:46
NGNode::getPosition
const Position & getPosition() const
Returns this node's position.
Definition: NGNode.h:87
MAX2
T MAX2(T a, T b)
Definition: StdDefs.h:80
RandomDistributor::get
T get(std::mt19937 *which=0) const
Draw a sample of the distribution.
Definition: RandomDistributor.h:111
NGRandomNetBuilder::checkAngles
bool checkAngles(NGNode *node)
Checks whether the angle of this node's connections are valid.
Definition: NGRandomNetBuilder.cpp:62
RandHelper::rand
static double rand(std::mt19937 *rng=0)
Returns a random real number in [0, 1)
Definition: RandHelper.h:60
NGNet
The class storing the generated network.
Definition: NGNet.h:50
GeomHelper::INVALID_OFFSET
static const double INVALID_OFFSET
a value to signify offsets outside the range of [0, Line.length()]
Definition: GeomHelper.h:52
NGRandomNetBuilder::removeOuterNode
void removeOuterNode(NGNode *node)
Removes the given node from the list of outer nodes.
Definition: NGRandomNetBuilder.cpp:51
Position
A point in 2D or 3D with translation and scaling methods.
Definition: Position.h:39
Position::x
double x() const
Returns the x-position.
Definition: Position.h:57
NGNet::nodeNo
int nodeNo() const
Returns the number of stored nodes.
Definition: NGNet.cpp:329
NGRandomNetBuilder.h
RandomDistributor< int >
Position::distanceTo2D
double distanceTo2D(const Position &p2) const
returns the euclidean distance in the x-y-plane
Definition: Position.h:244
NGRandomNetBuilder::myNumNodes
int myNumNodes
Number of nodes to be created.
Definition: NGRandomNetBuilder.h:150
NGRandomNetBuilder::createNewNode
bool createNewNode(NGNode *baseNode, bool gridMode)
Creates new random node.
Definition: NGRandomNetBuilder.cpp:173
NGNode::getMaxNeighbours
int getMaxNeighbours()
Returns this node's maximum neighbour number.
Definition: NGNode.h:96
GeomHelper::angle2D
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:84
Position::y
double y() const
Returns the y-position.
Definition: Position.h:62
NGRandomNetBuilder::myMaxDistance
double myMaxDistance
Maximum distance allowed between two nodes.
Definition: NGRandomNetBuilder.h:139
M_PI
#define M_PI
Definition: odrSpiral.cpp:40
PositionVector::positionAtOffset2D
Position positionAtOffset2D(double pos, double lateralOffset=0) const
Returns the position at the given length.
Definition: PositionVector.cpp:268
NGRandomNetBuilder::myOuterLinks
NGEdgeList myOuterLinks
The list of outer links.
Definition: NGRandomNetBuilder.h:123
NGRandomNetBuilder::createNet
void createNet(int numNodes, bool gridMode)
Builds a NGNet using the set values.
Definition: NGRandomNetBuilder.cpp:210
NGRandomNetBuilder::myNumTries
int myNumTries
Number of tries to create a new node.
Definition: NGRandomNetBuilder.h:147
config.h
GeomHelper.h
RandHelper.h
NGNode::setMaxNeighbours
void setMaxNeighbours(int value)
Sets this node's maximum neighbour number.
Definition: NGNode.h:105
StdDefs.h
NGNet::add
void add(NGNode *node)
Adds the given node to the network.
Definition: NGNet.cpp:317
NGNode::setY
void setY(double y)
Sets a new value for y-position.
Definition: NGNode.h:123
NGRandomNetBuilder::myOuterNodes
NGNodeList myOuterNodes
The list of outer nodes.
Definition: NGRandomNetBuilder.h:120
NGRandomNetBuilder::NGRandomNetBuilder
NGRandomNetBuilder(NGNet &net, double minAngle, double minDistance, double maxDistance, double connectivity, int numTries, const RandomDistributor< int > &neighborDist)
Constructor.
Definition: NGRandomNetBuilder.cpp:41
NGNode
A netgen-representation of a node.
Definition: NGNode.h:51
NGNode::setX
void setX(double x)
Sets a new value for x-position.
Definition: NGNode.h:114