Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 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 NBNodeCont.h
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Yun-Pang Floetteroed
18 : /// @author Michael Behrisch
19 : /// @author Walter Bamberger
20 : /// @date Tue, 20 Nov 2001
21 : ///
22 : // Container for nodes during the netbuilding process
23 : /****************************************************************************/
24 : #pragma once
25 : #include <config.h>
26 :
27 : #include <string>
28 : #include <map>
29 : #include <vector>
30 : #include <set>
31 : #include <utils/common/NamedRTree.h>
32 : #include <utils/geom/Position.h>
33 : #include "NBCont.h"
34 : #include "NBEdgeCont.h"
35 : #include "NBNode.h"
36 : #include <utils/common/UtilExceptions.h>
37 :
38 :
39 : // ===========================================================================
40 : // class declarations
41 : // ===========================================================================
42 : class NBDistrict;
43 : class OptionsCont;
44 : class OutputDevice;
45 : class NBParkingCont;
46 : class NBPTLineCont;
47 : class NBPTStopCont;
48 :
49 :
50 : // ===========================================================================
51 : // class definitions
52 : // ===========================================================================
53 : /**
54 : * @class NBNodeCont
55 : * @brief Container for nodes during the netbuilding process
56 : */
57 : class NBNodeCont {
58 :
59 : public:
60 : /// @brief Definition of a node cluster container
61 : typedef std::vector<NodeSet> NodeClusters;
62 : typedef std::pair<NBNode*, double> NodeAndDist;
63 20 : struct JoinCluster {
64 : std::set<std::string> cluster;
65 : NBNode* node;
66 : bool resetConnections;
67 : };
68 :
69 : /// @brief Constructor
70 2506 : NBNodeCont() {}
71 :
72 : /// @brief Destructor
73 : ~NBNodeCont();
74 :
75 : /// @name Insertion/removal/retrieval of nodes
76 : /// @{
77 : /** @brief Inserts a node into the map
78 : * @param[in] id The node's id
79 : * @param[in] position The node's position
80 : * @param[in] A district assigned to the node
81 : * @return Whether the node could be added (no other with the same id or position is stored)
82 : */
83 : bool insert(const std::string& id, const Position& position, NBDistrict* district = 0);
84 :
85 : /** @brief Inserts a node into the map
86 : * @param[in] node The node to insert
87 : * @return Whether the node could be added (no other with the same id or position is stored)
88 : */
89 : bool insert(NBNode* node);
90 :
91 : /** @brief Removes the given node, deleting it
92 : * @param[in] node The node to delete and remove
93 : * @return Whether the node could be removed (existed)
94 : */
95 : bool erase(NBNode* node);
96 :
97 : /** @brief Removes the given node but does not delete it
98 : * @param[in] node The node to delete and remove
99 : * @param[in] remember Whether to keep the node for future reference
100 : * @return Whether the node could be removed (existed)
101 : */
102 : bool extract(NBNode* node, bool remember = false);
103 :
104 : /** @brief Returns the node with the given name
105 : * @param[in] id The id of the node to retrieve
106 : * @return The node with the given id, or 0 if no such node exists
107 : */
108 : NBNode* retrieve(const std::string& id) const;
109 :
110 : /** @brief Returns the node with the given coordinates
111 : * @param[in] position The position at which the node to retrieve lies
112 : * @param[in] offset An offset which can be applied in the case positions are blurred
113 : * @return The node at the given position, or 0 if no such node exists
114 : */
115 : std::vector<NBNode*> retrieveByPos(const Position& position, const double offset = 0.) const;
116 :
117 : /// @brief Returns the pointer to the begin of the stored nodes
118 : std::map<std::string, NBNode*>::const_iterator begin() const {
119 : return myNodes.begin();
120 : }
121 :
122 : /// @brief Returns the pointer to the end of the stored nodes
123 : std::map<std::string, NBNode*>::const_iterator end() const {
124 : return myNodes.end();
125 : }
126 : /// @}
127 :
128 : /// @name Methods for joining nodes
129 : /// @{
130 : /* @brief add ids of nodes wich shall not be joined
131 : * @param[in] ids A list of ids to exclude from joining
132 : * @note it does not check whether the nodes exist because all nodes may not have been loaded yet
133 : */
134 : void addJoinExclusion(const std::vector<std::string>& ids);
135 :
136 : /// @brief if base is an existing node id, find a unused id of the form base + sep + INT
137 : std::string createUnusedID(const std::string& base, const std::string& sep);
138 :
139 : /** @brief generate id from cluster node ids
140 : * @param[in] cluster The cluster ids
141 : * @param[in] prefix The cluster prefix
142 : * @return the generated id
143 : */
144 882 : std::string createClusterId(const NodeSet& cluster, const std::string& prefix = "cluster_") {
145 : std::set<std::string> clusterIds;
146 3793 : for (NBNode* j : cluster) {
147 : clusterIds.insert(j->getID());
148 : }
149 1764 : return createClusterId(clusterIds, prefix);
150 : }
151 :
152 : /** @brief generate id from cluster node ids
153 : * @param[in] cluster The cluster ids
154 : * @param[in] prefix The cluster prefix
155 : * @return the generated id
156 : */
157 : std::string createClusterId(const std::set<std::string>& cluster, const std::string& prefix = "cluster_");
158 :
159 : /** @brief add ids of nodes which shall be joined into a single node
160 : * @param[in] cluster The cluster to add
161 : */
162 : void addCluster2Join(const std::set<std::string>& cluster, NBNode* node, const bool resetConnections=false);
163 :
164 : /// @brief Joins loaded junction clusters (see NIXMLNodesHandler)
165 : int joinLoadedClusters(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc);
166 :
167 : /// @brief Joins junctions that are very close together
168 : int joinJunctions(double maxDist, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, NBPTStopCont& sc);
169 :
170 : /// @brief Joins junctions with similar coordinates regardless of topology
171 : int joinSameJunctions(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, double maxDist);
172 :
173 : /// @brief return all cluster neighbors for the given node
174 : static NodeSet getClusterNeighbors(const NBNode* n, double longThreshold, NodeSet& cluster);
175 :
176 : /// @brief whether the given node may continue a slip lane
177 : static bool isSlipLaneContinuation(const NBNode* cont);
178 :
179 : /// @brief check whether the given node maybe the start of a slip lane
180 : bool maybeSlipLaneStart(const NBNode* n, EdgeVector& outgoing, double& inAngle) const;
181 : /// @brief check whether the given node maybe the end of a slip lane
182 : bool maybeSlipLaneEnd(const NBNode* n, EdgeVector& incoming, double& outAngle) const;
183 :
184 : /// @brief try to find a joinable subset (recursively)
185 : bool reduceToCircle(NodeSet& cluster, int circleSize, NodeSet startNodes, double maxDist, std::vector<NBNode*> cands = std::vector<NBNode*>()) const;
186 :
187 : /// @brief find closest neighbor for building circle
188 : NBEdge* shortestEdge(const NodeSet& cluster, const NodeSet& startNodes, const std::vector<NBNode*>& exclude) const;
189 : /// @}
190 :
191 : /// @name Adapting the input
192 : /// @{
193 : /** @brief Removes self-loop edges (edges where the source and the destination node are the same)
194 : * @param[in, opt. changed] dc The districts container to update
195 : * @param[in, opt. changed] ec The edge container to remove the edges from
196 : * @param[in, opt. changed] tc The traffic lights container to update
197 : * @post Each edge is a uni-directional connection between two different nodes
198 : * @return The number of removed edges
199 : */
200 : int removeSelfLoops(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tc);
201 :
202 : /** @brief Joins edges connecting the same nodes
203 : * @param[in, opt. changed] dc The districts container to update
204 : * @param[in, opt. changed] ec The edge container to remove the edges from
205 : * @param[in, opt. changed] tc The traffic lights container to update
206 : * @post No two edges with same geometry connecting same nodes exist
207 : */
208 : void joinSimilarEdges(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, bool removeDuplicates);
209 :
210 : /// @brief fix overlap
211 : void avoidOverlap();
212 :
213 : /** @brief Removes sequences of edges that are not connected with a junction.
214 : * Simple roads without junctions sometimes remain when converting from OpenStreetMap,
215 : * but they make no sense. Remaining empty nodes are also deleted.
216 : *
217 : * @param[in, opt. changed] dc The district container needed if edges shall be removed
218 : * @param[in, opt. changed] ec The container with the edge to be tested
219 : * @return The number of removed edges
220 : */
221 : int removeIsolatedRoads(NBDistrictCont& dc, NBEdgeCont& ec);
222 :
223 : /** @brief Checks the network for weak connectivity and removes all but the largest components.
224 : * The connectivity check is done regardless of edge direction and vclass.
225 : *
226 : * @param[in, opt. changed] dc The district container needed if edges shall be removed
227 : * @param[in, opt. changed] ec The container with the edge to be tested
228 : * @param[in] numKeep The number of components to keep
229 : * @return The number of removed edges
230 : */
231 : int removeComponents(NBDistrictCont& dc, NBEdgeCont& ec, const int numKeep, bool hasPTStops);
232 :
233 : /* @brief remove rail components after ptstops are built
234 : * @return The number of removed edges
235 : */
236 : int removeRailComponents(NBDistrictCont& dc, NBEdgeCont& ec, NBPTStopCont& sc);
237 :
238 : /** @brief Removes "unwished" nodes
239 : *
240 : * Removes nodes if a) no incoming/outgoing edges exist or
241 : * b) if the node is a "geometry" node. In the second case,
242 : * edges that participate at the node will be joined.
243 : * Whether the node is a geometry node or not, is determined
244 : * by a call to NBNode::checkIsRemovable.
245 : * The node is removed from the list of tls-controlled nodes.
246 : * @param[in, opt. changed] dc The district container needed if a node shall be removed
247 : * @param[in, opt. changed] ec The edge container needed for joining edges
248 : * @param[in, opt. changed] tlc The traffic lights container to remove nodes from
249 : * @param[in, opt. changed] sc The pt stops container to update stop edges
250 : * @param[in, opt. changed] pc The pt stops container to update stop edges
251 : * @param[in] removeGeometryNodes Whether geometry nodes shall also be removed
252 : * @return The number of removed nodes
253 : */
254 : int removeUnwishedNodes(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc,
255 : NBPTStopCont& sc, NBPTLineCont& lc, NBParkingCont& pc,
256 : bool removeGeometryNodes);
257 : /// @}
258 :
259 : /// @name Methods for guessing/computing traffic lights
260 : /// @{
261 : /** @brief Guesses which junctions or junction clusters shall be controlled by tls
262 : * @param[in] oc The options that steer the guessing process
263 : * @param[filled] tlc The traffic lights control into which new traffic light definitions shall be stored
264 : * @todo Recheck exception handling
265 : */
266 : void guessTLs(OptionsCont& oc, NBTrafficLightLogicCont& tlc);
267 :
268 : /// @brief recheck myGuessedTLS after node logics are computed
269 : void recheckGuessedTLS(NBTrafficLightLogicCont& tlc);
270 :
271 : /// @brief check whether a specific guessed tls should keep its type
272 : bool recheckTLSThreshold(NBNode* node);
273 :
274 : /// @brief compute keepClear status for all connections
275 : void computeKeepClear();
276 :
277 : /** @brief Builds clusters of tls-controlled junctions and joins the control if possible
278 : * @param[changed] tlc The traffic lights control for adding/removing new/prior tls
279 : * @param[in] maxdist The maximum distance between nodes for clustering
280 : * @todo Recheck exception handling
281 : */
282 : void joinTLS(NBTrafficLightLogicCont& tlc, double maxdist);
283 :
284 : /** @brief Sets the given node as being controlled by a tls
285 : * @param[in] node The node that shall be controlled by a tls
286 : * @param[in] tlc The traffic lights control into which the new traffic light definition shall be stored
287 : * @param[in] type The type of the new tls
288 : * @param[in] id The id of the tls to add
289 : * @todo Recheck exception handling
290 : */
291 : void setAsTLControlled(NBNode* node, NBTrafficLightLogicCont& tlc, TrafficLightType type, std::string id = "");
292 : /// @}
293 :
294 : /// @brief Returns whether the node with the id was deleted explicitly
295 : bool wasRemoved(std::string id) const {
296 : return myExtractedNodes.count(id) != 0;
297 : }
298 :
299 : /// @brief add prefix to all nodes
300 : void addPrefix(const std::string& prefix);
301 :
302 : /// @brief Renames the node. Throws exception if newID already exists
303 : void rename(NBNode* node, const std::string& newID);
304 :
305 : /// divides the incoming lanes on outgoing lanes
306 : void computeLanes2Lanes();
307 :
308 : /// @brief build the list of outgoing edges and lanes
309 : void computeLogics(const NBEdgeCont& ec);
310 :
311 : /// @brief compute right-of-way logic for all lane-to-lane connections
312 : void computeLogics2(const NBEdgeCont& ec, OptionsCont& oc);
313 :
314 : /// @brief Returns the number of nodes stored in this container
315 : int size() const {
316 4768 : return (int) myNodes.size();
317 : }
318 :
319 : /// @brief deletes all nodes
320 : void clear();
321 :
322 : /// @brief generates a new node ID
323 : std::string getFreeID();
324 :
325 : /** @brief Compute the junction shape for this node
326 : * @param[in] mismatchThreshold The threshold for warning about shapes which are away from myPosition
327 : */
328 : void computeNodeShapes(double mismatchThreshold = -1);
329 :
330 : /** @brief Prints statistics about built nodes
331 : *
332 : * Goes through stored nodes, computes the numbers of unregulated, priority and right-before-left
333 : * junctions and prints them.
334 : */
335 : void printBuiltNodesStatistics() const;
336 :
337 : /// @brief get all node names
338 : std::vector<std::string> getAllNames() const;
339 :
340 : /* @brief analyzes a cluster of nodes which shall be joined
341 : * @param[in] cluster The nodes to be joined
342 : * @param[out] id The name for the new node
343 : * @param[out] pos The position of the new node
344 : * @param[out] hasTLS Whether the new node has a traffic light
345 : * @param[out] tlType The type of traffic light (if any)
346 : */
347 : void analyzeCluster(NodeSet cluster, std::string& id, Position& pos,
348 : bool& hasTLS, TrafficLightType& type, SumoXMLNodeType& nodeType);
349 :
350 : /// @brief gets all joined clusters (see doc for myClusters2Join)
351 : void registerJoinedCluster(const NodeSet& cluster);
352 : void registerJoinedCluster(const std::set<std::string>& cluster);
353 :
354 : /// @brief remove cluster from list (on netedit-undo)
355 : void unregisterJoinedCluster(const std::set<std::string>& cluster);
356 :
357 : /// @brief gets all joined clusters (see doc for myClusters2Join)
358 : const std::vector<std::set<std::string> >& getJoinedClusters() const {
359 : return myJoinedClusters;
360 : }
361 :
362 : /* @brief discards traffic lights
363 : * @param[in] geometryLike Whether only tls at geometry-like nodes shall be discarded
364 : */
365 : void discardTrafficLights(NBTrafficLightLogicCont& tlc, bool geometryLike);
366 :
367 : /// @brief discards rail signals
368 : void discardRailSignals();
369 :
370 : /// @brief mark a node as being created form a split
371 : void markAsSplit(const NBNode* node) {
372 : mySplit.insert(node);
373 281 : }
374 :
375 : /// @brief mark a node as explicitly not controlled by a TLS
376 : void markAsNotTLS(const NBNode* node) {
377 : myUnsetTLS.insert(node);
378 41 : }
379 :
380 : /// @brief remap node IDs according to options --numerical-ids and --reserved-ids
381 : int remapIDs(bool numericaIDs, bool reservedIDs, bool keptIDs, const std::string& prefix, NBTrafficLightLogicCont& tlc);
382 :
383 : /// @brief guess and mark fringe nodes
384 : int guessFringe();
385 :
386 : /// @brief apply default values after loading
387 : void applyConditionalDefaults();
388 :
389 : /// @brief reset all node shapes
390 : bool resetNodeShapes();
391 :
392 : private:
393 :
394 : /// @name Helper methods for for joining nodes
395 : /// @{
396 : /** @brief Builds node clusters
397 : *
398 : * A node cluster is made up from nodes which are near by (distance<maxDist) and connected.
399 : *
400 : * @param[in] maxDist The maximum distance between two nodes for clustering
401 : * @param[in, filled] into The container to store the clusters in
402 : */
403 : void generateNodeClusters(double maxDist, NodeClusters& into) const;
404 :
405 : /// @brief remove geometry-like fringe nodes from cluster
406 : void pruneClusterFringe(NodeSet& cluster, double maxDist, bool remove2TLS = false) const;
407 :
408 : /// @brief avoid removal of long edges when joining junction clusters
409 : static int pruneLongEdges(NodeSet& cluster, double maxDist, const bool dryRun = false);
410 :
411 : /// @brief compute the maximum distance between any two cluster nodes
412 : static double getDiameter(const NodeSet& cluster);
413 :
414 : /// @brief check whether the node is geometryLike when only considering edges that support the given permissions
415 : static bool geometryLikeForClass(const NBNode* n, SVCPermissions permissions);
416 :
417 : /// @brief remove nodes that form a slip lane from cluster
418 : void pruneSlipLaneNodes(NodeSet& cluster, double maxDist) const;
419 :
420 : /// @brief determine wether the cluster is not too complex for joining
421 : bool feasibleCluster(const NodeSet& cluster, const std::map<const NBNode*, std::vector<NBNode*> >& ptStopEnds,
422 : double maxDist, std::string& reason, NBNode*& tryRemove) const;
423 :
424 : /// @brief joins the given node clusters
425 : void joinNodeClusters(NodeClusters clusters, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, bool resetConnections = false);
426 : void joinNodeCluster(NodeSet clusters, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc,
427 : NBNode* predefined = nullptr, bool resetConnections = false);
428 :
429 : /// @}
430 :
431 : /// @name Helper methods for guessing/computing traffic lights
432 : /// @{
433 : /** @brief Returns whethe the given node cluster should be controlled by a tls
434 : * @param[in] c The node cluster
435 : * @param[in] laneSpeedThreshold threshold for determining whether a node or cluster should be tls controlled
436 : * @return Whether this node cluster shall be controlled by a tls
437 : */
438 : bool shouldBeTLSControlled(const NodeSet& c, double laneSpeedThreshold, bool recheck = false) const;
439 :
440 : /// @brief check wheter the set of nodes only contains pedestrian crossings
441 : bool onlyCrossings(const NodeSet& c) const;
442 :
443 : /// @brief check wheter the set of nodes contains traffic lights with custom id
444 : bool customTLID(const NodeSet& c) const;
445 : /// @}
446 :
447 : /// @brief update pareto frontier with the given node
448 : void paretoCheck(NBNode* node, NodeSet& frontier, int xSign, int ySign);
449 :
450 : /// @brief Definition of the map of names to nodes
451 : typedef std::map<std::string, NBNode*> NodeCont;
452 :
453 : /// @brief The map of names to nodes
454 : NodeCont myNodes;
455 :
456 : /// @brief The extracted nodes which are kept for reference
457 : NodeCont myExtractedNodes;
458 :
459 : /// @brief set of node ids which should not be joined
460 : std::set<std::string> myJoinExclusions;
461 :
462 : /// @brief loaded sets of node ids to join (cleared after use)
463 : std::vector<JoinCluster> myClusters2Join;
464 :
465 : /// @brief sets of node ids which were joined
466 : std::vector<std::set<std::string> > myJoinedClusters;
467 :
468 : /// @brief ids found in loaded join clusters used for error checking
469 : std::set<std::string> myJoined;
470 :
471 : /// @brief nodes that were created when splitting an edge
472 : std::set<const NBNode*> mySplit;
473 :
474 : /// @brief nodes that received a traffic light due to guessing (--tls.guess)
475 : std::set<NBNode*, ComparatorIdLess> myGuessedTLS;
476 :
477 : /// @brief nodes that are excluded from tls-guessing
478 : std::set<const NBNode*> myUnsetTLS;
479 :
480 : /// @brief node positions for faster lookup
481 : NamedRTree myRTree;
482 :
483 : /// @brief network components that must be removed if not connected to the road network via stop access
484 : std::vector<std::vector<std::string> > myRailComponents;
485 :
486 : /// @brief invalidated copy constructor
487 : NBNodeCont(const NBNodeCont& s) = delete;
488 :
489 : /// @brief invalidated assignment operator
490 : NBNodeCont& operator=(const NBNodeCont& s) = delete;
491 : };
|
