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