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