Eclipse SUMO - Simulation of Urban MObility
Loading...
Searching...
No Matches
NGRandomNetBuilder.cpp
Go to the documentation of this file.
1/****************************************************************************/
2// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3// Copyright (C) 2001-2024 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"
31
32
33// ===========================================================================
34// method definitions
35// ===========================================================================
36// ---------------------------------------------------------------------------
37// NGRandomNetBuilder-definitions
38// ---------------------------------------------------------------------------
39NGRandomNetBuilder::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
48void
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
59bool
61 bool check = true;
62
63 if (node->getLinks().size() > 1) {
64 // loop over all links
65 NGNode* ni;
66 for (NGEdge* const li : node->getLinks()) {
67 // calc vector of currentnode
68 if (li->getStartNode() == node) {
69 ni = li->getEndNode();
70 } else {
71 ni = li->getStartNode();
72 }
73 Position v1(
74 ni->getPosition().x() - node->getPosition().x(),
75 ni->getPosition().y() - node->getPosition().y());
76 // loop over all links
77 for (NGEdge* const lj : node->getLinks()) {
78 if (li != lj) {
79 if (lj->getStartNode() == node) {
80 ni = lj->getEndNode();
81 } else {
82 ni = lj->getStartNode();
83 }
84 Position v2(
85 ni->getPosition().x() - node->getPosition().x(),
86 ni->getPosition().y() - node->getPosition().y());
87 if (fabs(GeomHelper::angle2D(v1, v2)) < myMinLinkAngle) {
88 check = false;
89 }
90 }
91 }
92 }
93 }
94 return check;
95}
96
97
98bool
100 bool connectable = true;
101 const PositionVector n(baseNode->getPosition(), newNode->getPosition());
102
103 // check for range between Basenode and Newnode
104 if (connectable) {
105 double dist = n.length();
106 if ((dist < myMinDistance) || (dist > myMaxDistance)) {
107 connectable = false;
108 }
109 }
110
111 // check for angle restrictions
112 if (connectable) {
113 connectable = checkAngles(baseNode);
114 }
115 if (connectable) {
116 connectable = checkAngles(newNode);
117 }
118
119 // check for intersections and range restrictions with outer links
120 if (connectable) {
121 NGEdgeList::iterator li;
122 li = myOuterLinks.begin();
123 while (connectable && (li != myOuterLinks.end())) {
124 // check intersection only if links don't share a node
125 const NGNode* const start = (*li)->getStartNode();
126 const NGNode* const end = (*li)->getEndNode();
127 const Position& p1 = start->getPosition();
128 const Position& p2 = end->getPosition();
129 if ((baseNode != start) && (baseNode != end) && (newNode != start) && (newNode != end)) {
130 connectable = !n.intersects(p1, p2);
131 }
132 // check NewNode-To-Links distance only, if NewNode isn't part of link
133 if (connectable && (newNode != start) && (newNode != end)) {
134 const double offset = GeomHelper::nearest_offset_on_line_to_point2D(p1, p2, n[1]);
135 if (offset != GeomHelper::INVALID_OFFSET) {
136 const Position p = PositionVector(p1, p2).positionAtOffset2D(offset);
137 const double dist = p.distanceTo2D(n[1]);
138 if (dist < myMinDistance) {
139 connectable = false;
140 }
141 }
142 }
143 ++li;
144 }
145 }
146 return connectable;
147}
148
149
150void
152 myConNodes.clear();
153 NGNodeList::iterator ni;
154 for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
155 NGNode* on = *ni;
156 if (!node->connected(on)) {
157 if ((node->getMaxNeighbours() > (int)node->getLinks().size()) &&
158 (on->getMaxNeighbours() > (int)on->getLinks().size())) {
159 if (canConnect(node, on)) {
160 myConNodes.push_back(on);
161 }
162 }
163 }
164 }
165}
166
167
168bool
169NGRandomNetBuilder::createNewNode(NGNode* baseNode, bool gridMode) {
170 // calculate position of new node based on BaseNode
172 double angle = RandHelper::rand((double)(2 * M_PI));
173 if (gridMode) {
174 // dist must be a multiple of minDist
175 dist = MAX2(1, int(dist / myMinDistance)) * myMinDistance;
176 // angle must be a multiple of 90 degrees
177 angle = RandHelper::rand(4) * 0.5 * M_PI;
178 }
179 double x = baseNode->getPosition().x() + dist * cos(angle);
180 double y = baseNode->getPosition().y() + dist * sin(angle);
181 NGNode* newNode = new NGNode(myNet.getNextFreeID());
182 newNode->setX(x);
183 newNode->setY(y);
185 NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
186 if (canConnect(baseNode, newNode)) {
187 // add node
188 myNet.add(newNode);
189 myOuterNodes.push_front(newNode);
190 // add link
191 myNet.add(newLink);
192 myOuterLinks.push_back(newLink);
193 // check basenode for being outer node
194 if ((int)baseNode->getLinks().size() >= baseNode->getMaxNeighbours()) {
195 removeOuterNode(baseNode);
196 }
197 return true;
198 } else {
199 delete newLink;
200 delete newNode;
201 return false;
202 }
203}
204
205
206void
207NGRandomNetBuilder::createNet(int numNodes, bool gridMode) {
208 myNumNodes = numNodes;
209
210 NGNode* outerNode = new NGNode(myNet.getNextFreeID());
211 outerNode->setX(0);
212 outerNode->setY(0);
213 outerNode->setMaxNeighbours(4);
214
215 myNet.add(outerNode);
216 myOuterNodes.push_back(outerNode);
217
218 bool created = true;
219 while ((myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
220 // brings last element to front
221 if (!created) {
222 myOuterNodes.push_front(myOuterNodes.back());
223 myOuterNodes.pop_back();
224 }
225 outerNode = myOuterNodes.back();
226 findPossibleOuterNodes(outerNode);
227 created = false;
228 if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
229 // create link
230 NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
231 if (canConnect(outerNode, myConNodes.back())) {
232 // add link
233 myNet.add(newLink);
234 myOuterLinks.push_back(newLink);
235 // check nodes for being outer node
236 if ((int)outerNode->getLinks().size() >= outerNode->getMaxNeighbours()) {
237 removeOuterNode(outerNode);
238 }
239 if ((int)myConNodes.back()->getLinks().size() >= myConNodes.back()->getMaxNeighbours()) {
241 }
242 created = true;
243 } else {
244 delete newLink;
245 }
246 } else {
247 int count = 0;
248 do {
249 created = createNewNode(outerNode, gridMode);
250 count++;
251 } while ((count <= myNumTries) && !created);
252 if (!created) {
253 outerNode->setMaxNeighbours((int)outerNode->getLinks().size());
254 myOuterNodes.remove(outerNode);
255 }
256 }
257 }
258}
259
260
261/****************************************************************************/
T MAX2(T a, T b)
Definition StdDefs.h:82
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,...
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)
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:313
int nodeNo() const
Returns the number of stored nodes.
Definition NGNet.cpp:325
std::string getNextFreeID()
Returns the next free id.
Definition NGNet.cpp:64
A netgen-representation of a node.
Definition NGNode.h:48
bool connected(const NGNode *const node, const bool withDir=false) 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
const NGEdgeList & getLinks() const
Definition NGNode.h:164
void setMaxNeighbours(int value)
Sets this node's maximum neighbour number.
Definition NGNode.h:102
const Position & getPosition() const
Returns this node's position.
Definition NGNode.h:84
int getMaxNeighbours()
Returns this node's maximum neighbour number.
Definition NGNode.h:93
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.
bool checkAngles(const NGNode *const node)
Checks whether the angle of this node's connections are valid.
double myMinLinkAngle
Minimum angle allowed between two links.
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:37
double distanceTo2D(const Position &p2) const
returns the euclidean distance in the x-y-plane
Definition Position.h:276
double x() const
Returns the x-position.
Definition Position.h:55
double y() const
Returns the y-position.
Definition Position.h:60
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(SumoRNG *rng=nullptr)
Returns a random real number in [0, 1)
Represents a generic random distribution.
T get(SumoRNG *which=nullptr) const
Draw a sample of the distribution.
#define M_PI
Definition odrSpiral.cpp:45