Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2025 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 : /****************************************************************************/
14 : /// @file NGRandomNetBuilder.cpp
15 : /// @author Markus Hartinger
16 : /// @author Daniel Krajzewicz
17 : /// @author Michael Behrisch
18 : /// @date Mar, 2003
19 : ///
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>
30 : #include <utils/common/RandHelper.h>
31 :
32 :
33 : // ===========================================================================
34 : // method definitions
35 : // ===========================================================================
36 : // ---------------------------------------------------------------------------
37 : // NGRandomNetBuilder-definitions
38 : // ---------------------------------------------------------------------------
39 24 : NGRandomNetBuilder::NGRandomNetBuilder(NGNet& net, double minAngle, double minDistance,
40 : double maxDistance, double connectivity,
41 24 : int numTries, const RandomDistributor<int>& neighborDist)
42 24 : : myNet(net), myMinLinkAngle(minAngle), myMinDistance(minDistance),
43 24 : myMaxDistance(maxDistance), myConnectivity(connectivity), myNumTries(numTries),
44 24 : myNeighbourDistribution(neighborDist) {
45 24 : }
46 :
47 :
48 : void
49 1657 : NGRandomNetBuilder::removeOuterNode(NGNode* node) {
50 60984 : for (NGNodeList::iterator ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
51 60984 : if (*ni == node) {
52 1657 : myOuterNodes.erase(ni);
53 : return;
54 : }
55 : }
56 : }
57 :
58 :
59 : bool
60 91617 : NGRandomNetBuilder::checkAngles(const NGNode* const node) {
61 : bool check = true;
62 :
63 91617 : if (node->getLinks().size() > 1) {
64 : // loop over all links
65 : NGNode* ni;
66 262944 : for (NGEdge* const li : node->getLinks()) {
67 : // calc vector of currentnode
68 198288 : 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 198288 : ni->getPosition().y() - node->getPosition().y());
76 : // loop over all links
77 876170 : for (NGEdge* const lj : node->getLinks()) {
78 677882 : if (li != lj) {
79 479594 : 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 479594 : ni->getPosition().y() - node->getPosition().y());
87 479594 : if (fabs(GeomHelper::angle2D(v1, v2)) < myMinLinkAngle) {
88 : check = false;
89 : }
90 : }
91 : }
92 : }
93 : }
94 91617 : return check;
95 : }
96 :
97 :
98 : bool
99 453348 : NGRandomNetBuilder::canConnect(NGNode* baseNode, NGNode* newNode) {
100 : bool connectable = true;
101 453348 : const PositionVector n(baseNode->getPosition(), newNode->getPosition());
102 :
103 : // check for range between Basenode and Newnode
104 : if (connectable) {
105 453348 : double dist = n.length();
106 453348 : if ((dist < myMinDistance) || (dist > myMaxDistance)) {
107 : connectable = false;
108 : }
109 : }
110 :
111 : // check for angle restrictions
112 : if (connectable) {
113 57913 : connectable = checkAngles(baseNode);
114 : }
115 57913 : if (connectable) {
116 33704 : connectable = checkAngles(newNode);
117 : }
118 :
119 : // check for intersections and range restrictions with outer links
120 33704 : if (connectable) {
121 : NGEdgeList::iterator li;
122 : li = myOuterLinks.begin();
123 3316104 : while (connectable && (li != myOuterLinks.end())) {
124 : // check intersection only if links don't share a node
125 3285358 : 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 3285358 : if ((baseNode != start) && (baseNode != end) && (newNode != start) && (newNode != end)) {
130 3217328 : connectable = !n.intersects(p1, p2);
131 : }
132 : // check NewNode-To-Links distance only, if NewNode isn't part of link
133 3285358 : if (connectable && (newNode != start) && (newNode != end)) {
134 3250938 : const double offset = GeomHelper::nearest_offset_on_line_to_point2D(p1, p2, n[1]);
135 3250938 : if (offset != GeomHelper::INVALID_OFFSET) {
136 265467 : const Position p = PositionVector(p1, p2).positionAtOffset2D(offset);
137 265467 : const double dist = p.distanceTo2D(n[1]);
138 265467 : if (dist < myMinDistance) {
139 : connectable = false;
140 : }
141 : }
142 : }
143 : ++li;
144 : }
145 : }
146 453348 : return connectable;
147 453348 : }
148 :
149 :
150 : void
151 11740 : NGRandomNetBuilder::findPossibleOuterNodes(NGNode* node) {
152 : myConNodes.clear();
153 : NGNodeList::iterator ni;
154 430412 : for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
155 418672 : NGNode* on = *ni;
156 418672 : if (!node->connected(on)) {
157 412499 : if ((node->getMaxNeighbours() > (int)node->getLinks().size()) &&
158 412499 : (on->getMaxNeighbours() > (int)on->getLinks().size())) {
159 412499 : if (canConnect(node, on)) {
160 13794 : myConNodes.push_back(on);
161 : }
162 : }
163 : }
164 : }
165 11740 : }
166 :
167 :
168 : bool
169 32482 : NGRandomNetBuilder::createNewNode(NGNode* baseNode, bool gridMode) {
170 : // calculate position of new node based on BaseNode
171 32482 : double dist = RandHelper::rand(myMinDistance, myMaxDistance);
172 : double angle = RandHelper::rand((double)(2 * M_PI));
173 32482 : if (gridMode) {
174 : // dist must be a multiple of minDist
175 7341 : dist = MAX2(1, int(dist / myMinDistance)) * myMinDistance;
176 : // angle must be a multiple of 90 degrees
177 7341 : angle = RandHelper::rand(4) * 0.5 * M_PI;
178 : }
179 32482 : double x = baseNode->getPosition().x() + dist * cos(angle);
180 32482 : double y = baseNode->getPosition().y() + dist * sin(angle);
181 32482 : NGNode* newNode = new NGNode(myNet.getNextFreeID());
182 : newNode->setX(x);
183 : newNode->setY(y);
184 32482 : newNode->setMaxNeighbours(myNeighbourDistribution.get());
185 32482 : NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
186 32482 : if (canConnect(baseNode, newNode)) {
187 : // add node
188 2998 : myNet.add(newNode);
189 2998 : myOuterNodes.push_front(newNode);
190 : // add link
191 2998 : myNet.add(newLink);
192 2998 : myOuterLinks.push_back(newLink);
193 : // check basenode for being outer node
194 2998 : if ((int)baseNode->getLinks().size() >= baseNode->getMaxNeighbours()) {
195 1238 : removeOuterNode(baseNode);
196 : }
197 2998 : return true;
198 : } else {
199 29484 : delete newLink;
200 29484 : delete newNode;
201 29484 : return false;
202 : }
203 : }
204 :
205 :
206 : void
207 24 : NGRandomNetBuilder::createNet(int numNodes, bool gridMode) {
208 24 : myNumNodes = numNodes;
209 :
210 24 : NGNode* outerNode = new NGNode(myNet.getNextFreeID());
211 : outerNode->setX(0);
212 : outerNode->setY(0);
213 : outerNode->setMaxNeighbours(4);
214 :
215 24 : myNet.add(outerNode);
216 24 : myOuterNodes.push_back(outerNode);
217 :
218 : bool created = true;
219 11764 : while ((myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
220 : // brings last element to front
221 11740 : if (!created) {
222 : myOuterNodes.push_front(myOuterNodes.back());
223 : myOuterNodes.pop_back();
224 : }
225 11740 : outerNode = myOuterNodes.back();
226 11740 : findPossibleOuterNodes(outerNode);
227 : created = false;
228 11740 : if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
229 : // create link
230 8367 : NGEdge* newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
231 8367 : if (canConnect(outerNode, myConNodes.back())) {
232 : // add link
233 1180 : myNet.add(newLink);
234 1180 : myOuterLinks.push_back(newLink);
235 : // check nodes for being outer node
236 1180 : if ((int)outerNode->getLinks().size() >= outerNode->getMaxNeighbours()) {
237 256 : removeOuterNode(outerNode);
238 : }
239 1180 : if ((int)myConNodes.back()->getLinks().size() >= myConNodes.back()->getMaxNeighbours()) {
240 163 : removeOuterNode(myConNodes.back());
241 : }
242 : created = true;
243 : } else {
244 7187 : delete newLink;
245 : }
246 : } else {
247 : int count = 0;
248 : do {
249 32482 : created = createNewNode(outerNode, gridMode);
250 32482 : count++;
251 32482 : } while ((count <= myNumTries) && !created);
252 3373 : if (!created) {
253 375 : outerNode->setMaxNeighbours((int)outerNode->getLinks().size());
254 375 : myOuterNodes.remove(outerNode);
255 : }
256 : }
257 : }
258 24 : }
259 :
260 :
261 : /****************************************************************************/
|
