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 2483 : 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 generate id from cluster node ids
137 : * @param[in] cluster The cluster ids
138 : * @param[in] prefix The cluster prefix
139 : * @return the generated id
140 : */
141 881 : std::string createClusterId(const NodeSet& cluster, const std::string& prefix = "cluster_") {
142 : std::set<std::string> clusterIds;
143 3787 : for (NBNode* j : cluster) {
144 : clusterIds.insert(j->getID());
145 : }
146 1762 : return createClusterId(clusterIds, prefix);
147 : }
148 :
149 : /** @brief generate id from cluster node ids
150 : * @param[in] cluster The cluster ids
151 : * @param[in] prefix The cluster prefix
152 : * @return the generated id
153 : */
154 : std::string createClusterId(const std::set<std::string>& cluster, const std::string& prefix = "cluster_");
155 :
156 : /** @brief add ids of nodes which shall be joined into a single node
157 : * @param[in] cluster The cluster to add
158 : */
159 : void addCluster2Join(const std::set<std::string>& cluster, NBNode* node, const bool resetConnections=false);
160 :
161 : /// @brief Joins loaded junction clusters (see NIXMLNodesHandler)
162 : int joinLoadedClusters(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc);
163 :
164 : /// @brief Joins junctions that are very close together
165 : int joinJunctions(double maxDist, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, NBPTStopCont& sc);
166 :
167 : /// @brief Joins junctions with similar coordinates regardless of topology
168 : int joinSameJunctions(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, double maxDist);
169 :
170 : /// @brief return all cluster neighbors for the given node
171 : static NodeSet getClusterNeighbors(const NBNode* n, double longThreshold, NodeSet& cluster);
172 :
173 : /// @brief whether the given node may continue a slip lane
174 : static bool isSlipLaneContinuation(const NBNode* cont);
175 :
176 : /// @brief check whether the given node maybe the start of a slip lane
177 : bool maybeSlipLaneStart(const NBNode* n, EdgeVector& outgoing, double& inAngle) const;
178 : /// @brief check whether the given node maybe the end of a slip lane
179 : bool maybeSlipLaneEnd(const NBNode* n, EdgeVector& incoming, double& outAngle) const;
180 :
181 : /// @brief try to find a joinable subset (recursively)
182 : bool reduceToCircle(NodeSet& cluster, int circleSize, NodeSet startNodes, double maxDist, std::vector<NBNode*> cands = std::vector<NBNode*>()) const;
183 :
184 : /// @brief find closest neighbor for building circle
185 : NBEdge* shortestEdge(const NodeSet& cluster, const NodeSet& startNodes, const std::vector<NBNode*>& exclude) const;
186 : /// @}
187 :
188 : /// @name Adapting the input
189 : /// @{
190 : /** @brief Removes self-loop edges (edges where the source and the destination node are the same)
191 : * @param[in, opt. changed] dc The districts container to update
192 : * @param[in, opt. changed] ec The edge container to remove the edges from
193 : * @param[in, opt. changed] tc The traffic lights container to update
194 : * @post Each edge is a uni-directional connection between two different nodes
195 : * @return The number of removed edges
196 : */
197 : int removeSelfLoops(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tc);
198 :
199 : /** @brief Joins edges connecting the same nodes
200 : * @param[in, opt. changed] dc The districts container to update
201 : * @param[in, opt. changed] ec The edge container to remove the edges from
202 : * @param[in, opt. changed] tc The traffic lights container to update
203 : * @post No two edges with same geometry connecting same nodes exist
204 : */
205 : void joinSimilarEdges(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, bool removeDuplicates);
206 :
207 : /// @brief fix overlap
208 : void avoidOverlap();
209 :
210 : /** @brief Removes sequences of edges that are not connected with a junction.
211 : * Simple roads without junctions sometimes remain when converting from OpenStreetMap,
212 : * but they make no sense. Remaining empty nodes are also deleted.
213 : *
214 : * @param[in, opt. changed] dc The district container needed if edges shall be removed
215 : * @param[in, opt. changed] ec The container with the edge to be tested
216 : * @return The number of removed edges
217 : */
218 : int removeIsolatedRoads(NBDistrictCont& dc, NBEdgeCont& ec);
219 :
220 : /** @brief Checks the network for weak connectivity and removes all but the largest components.
221 : * The connectivity check is done regardless of edge direction and vclass.
222 : *
223 : * @param[in, opt. changed] dc The district container needed if edges shall be removed
224 : * @param[in, opt. changed] ec The container with the edge to be tested
225 : * @param[in] numKeep The number of components to keep
226 : * @return The number of removed edges
227 : */
228 : int removeComponents(NBDistrictCont& dc, NBEdgeCont& ec, const int numKeep, bool hasPTStops);
229 :
230 : /* @brief remove rail components after ptstops are built
231 : * @return The number of removed edges
232 : */
233 : int removeRailComponents(NBDistrictCont& dc, NBEdgeCont& ec, NBPTStopCont& sc);
234 :
235 : /** @brief Removes "unwished" nodes
236 : *
237 : * Removes nodes if a) no incoming/outgoing edges exist or
238 : * b) if the node is a "geometry" node. In the second case,
239 : * edges that participate at the node will be joined.
240 : * Whether the node is a geometry node or not, is determined
241 : * by a call to NBNode::checkIsRemovable.
242 : * The node is removed from the list of tls-controlled nodes.
243 : * @param[in, opt. changed] dc The district container needed if a node shall be removed
244 : * @param[in, opt. changed] ec The edge container needed for joining edges
245 : * @param[in, opt. changed] tlc The traffic lights container to remove nodes from
246 : * @param[in, opt. changed] sc The pt stops container to update stop edges
247 : * @param[in, opt. changed] pc The pt stops container to update stop edges
248 : * @param[in] removeGeometryNodes Whether geometry nodes shall also be removed
249 : * @return The number of removed nodes
250 : */
251 : int removeUnwishedNodes(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc,
252 : NBPTStopCont& sc, NBPTLineCont& lc, NBParkingCont& pc,
253 : bool removeGeometryNodes);
254 : /// @}
255 :
256 : /// @name Methods for guessing/computing traffic lights
257 : /// @{
258 : /** @brief Guesses which junctions or junction clusters shall be controlled by tls
259 : * @param[in] oc The options that steer the guessing process
260 : * @param[filled] tlc The traffic lights control into which new traffic light definitions shall be stored
261 : * @todo Recheck exception handling
262 : */
263 : void guessTLs(OptionsCont& oc, NBTrafficLightLogicCont& tlc);
264 :
265 : /// @brief recheck myGuessedTLS after node logics are computed
266 : void recheckGuessedTLS(NBTrafficLightLogicCont& tlc);
267 :
268 : /// @brief check whether a specific guessed tls should keep its type
269 : bool recheckTLSThreshold(NBNode* node);
270 :
271 : /// @brief compute keepClear status for all connections
272 : void computeKeepClear();
273 :
274 : /** @brief Builds clusters of tls-controlled junctions and joins the control if possible
275 : * @param[changed] tlc The traffic lights control for adding/removing new/prior tls
276 : * @param[in] maxdist The maximum distance between nodes for clustering
277 : * @todo Recheck exception handling
278 : */
279 : void joinTLS(NBTrafficLightLogicCont& tlc, double maxdist);
280 :
281 : /** @brief Sets the given node as being controlled by a tls
282 : * @param[in] node The node that shall be controlled by a tls
283 : * @param[in] tlc The traffic lights control into which the new traffic light definition shall be stored
284 : * @param[in] type The type of the new tls
285 : * @param[in] id The id of the tls to add
286 : * @todo Recheck exception handling
287 : */
288 : void setAsTLControlled(NBNode* node, NBTrafficLightLogicCont& tlc, TrafficLightType type, std::string id = "");
289 : /// @}
290 :
291 : /// @brief Returns whether the node with the id was deleted explicitly
292 : bool wasRemoved(std::string id) const {
293 : return myExtractedNodes.count(id) != 0;
294 : }
295 :
296 : /// @brief add prefix to all nodes
297 : void addPrefix(const std::string& prefix);
298 :
299 : /// @brief Renames the node. Throws exception if newID already exists
300 : void rename(NBNode* node, const std::string& newID);
301 :
302 : /// divides the incoming lanes on outgoing lanes
303 : void computeLanes2Lanes();
304 :
305 : /// @brief build the list of outgoing edges and lanes
306 : void computeLogics(const NBEdgeCont& ec);
307 :
308 : /// @brief compute right-of-way logic for all lane-to-lane connections
309 : void computeLogics2(const NBEdgeCont& ec, OptionsCont& oc);
310 :
311 : /// @brief Returns the number of nodes stored in this container
312 : int size() const {
313 4722 : return (int) myNodes.size();
314 : }
315 :
316 : /// @brief deletes all nodes
317 : void clear();
318 :
319 : /// @brief generates a new node ID
320 : std::string getFreeID();
321 :
322 : /** @brief Compute the junction shape for this node
323 : * @param[in] mismatchThreshold The threshold for warning about shapes which are away from myPosition
324 : */
325 : void computeNodeShapes(double mismatchThreshold = -1);
326 :
327 : /** @brief Prints statistics about built nodes
328 : *
329 : * Goes through stored nodes, computes the numbers of unregulated, priority and right-before-left
330 : * junctions and prints them.
331 : */
332 : void printBuiltNodesStatistics() const;
333 :
334 : /// @brief get all node names
335 : std::vector<std::string> getAllNames() const;
336 :
337 : /* @brief analyzes a cluster of nodes which shall be joined
338 : * @param[in] cluster The nodes to be joined
339 : * @param[out] id The name for the new node
340 : * @param[out] pos The position of the new node
341 : * @param[out] hasTLS Whether the new node has a traffic light
342 : * @param[out] tlType The type of traffic light (if any)
343 : */
344 : void analyzeCluster(NodeSet cluster, std::string& id, Position& pos,
345 : bool& hasTLS, TrafficLightType& type, SumoXMLNodeType& nodeType);
346 :
347 : /// @brief gets all joined clusters (see doc for myClusters2Join)
348 : void registerJoinedCluster(const NodeSet& cluster);
349 : void registerJoinedCluster(const std::set<std::string>& cluster);
350 :
351 : /// @brief remove cluster from list (on netedit-undo)
352 : void unregisterJoinedCluster(const std::set<std::string>& cluster);
353 :
354 : /// @brief gets all joined clusters (see doc for myClusters2Join)
355 : const std::vector<std::set<std::string> >& getJoinedClusters() const {
356 : return myJoinedClusters;
357 : }
358 :
359 : /* @brief discards traffic lights
360 : * @param[in] geometryLike Whether only tls at geometry-like nodes shall be discarded
361 : */
362 : void discardTrafficLights(NBTrafficLightLogicCont& tlc, bool geometryLike);
363 :
364 : /// @brief discards rail signals
365 : void discardRailSignals();
366 :
367 : /// @brief mark a node as being created form a split
368 : void markAsSplit(const NBNode* node) {
369 : mySplit.insert(node);
370 281 : }
371 :
372 : /// @brief mark a node as explicitly not controlled by a TLS
373 : void markAsNotTLS(const NBNode* node) {
374 : myUnsetTLS.insert(node);
375 37 : }
376 :
377 : /// @brief remap node IDs according to options --numerical-ids and --reserved-ids
378 : int remapIDs(bool numericaIDs, bool reservedIDs, bool keptIDs, const std::string& prefix, NBTrafficLightLogicCont& tlc);
379 :
380 : /// @brief guess and mark fringe nodes
381 : int guessFringe();
382 :
383 : /// @brief apply default values after loading
384 : void applyConditionalDefaults();
385 :
386 : /// @brief reset all node shapes
387 : bool resetNodeShapes();
388 :
389 : private:
390 :
391 : /// @name Helper methods for for joining nodes
392 : /// @{
393 : /** @brief Builds node clusters
394 : *
395 : * A node cluster is made up from nodes which are near by (distance<maxDist) and connected.
396 : *
397 : * @param[in] maxDist The maximum distance between two nodes for clustering
398 : * @param[in, filled] into The container to store the clusters in
399 : */
400 : void generateNodeClusters(double maxDist, NodeClusters& into) const;
401 :
402 : /// @brief remove geometry-like fringe nodes from cluster
403 : void pruneClusterFringe(NodeSet& cluster, double maxDist, bool remove2TLS = false) const;
404 :
405 : /// @brief avoid removal of long edges when joining junction clusters
406 : static int pruneLongEdges(NodeSet& cluster, double maxDist, const bool dryRun = false);
407 :
408 : /// @brief compute the maximum distance between any two cluster nodes
409 : static double getDiameter(const NodeSet& cluster);
410 :
411 : /// @brief check whether the node is geometryLike when only considering edges that support the given permissions
412 : static bool geometryLikeForClass(const NBNode* n, SVCPermissions permissions);
413 :
414 : /// @brief remove nodes that form a slip lane from cluster
415 : void pruneSlipLaneNodes(NodeSet& cluster, double maxDist) const;
416 :
417 : /// @brief determine wether the cluster is not too complex for joining
418 : bool feasibleCluster(const NodeSet& cluster, const std::map<const NBNode*, std::vector<NBNode*> >& ptStopEnds,
419 : double maxDist, std::string& reason, NBNode*& tryRemove) const;
420 :
421 : /// @brief joins the given node clusters
422 : void joinNodeClusters(NodeClusters clusters, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, bool resetConnections = false);
423 : void joinNodeCluster(NodeSet clusters, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc,
424 : NBNode* predefined = nullptr, bool resetConnections = false);
425 :
426 : /// @}
427 :
428 : /// @name Helper methods for guessing/computing traffic lights
429 : /// @{
430 : /** @brief Returns whethe the given node cluster should be controlled by a tls
431 : * @param[in] c The node cluster
432 : * @param[in] laneSpeedThreshold threshold for determining whether a node or cluster should be tls controlled
433 : * @return Whether this node cluster shall be controlled by a tls
434 : */
435 : bool shouldBeTLSControlled(const NodeSet& c, double laneSpeedThreshold, bool recheck = false) const;
436 :
437 : /// @brief check wheter the set of nodes only contains pedestrian crossings
438 : bool onlyCrossings(const NodeSet& c) const;
439 :
440 : /// @brief check wheter the set of nodes contains traffic lights with custom id
441 : bool customTLID(const NodeSet& c) const;
442 : /// @}
443 :
444 : /// @brief update pareto frontier with the given node
445 : void paretoCheck(NBNode* node, NodeSet& frontier, int xSign, int ySign);
446 :
447 : /// @brief Definition of the map of names to nodes
448 : typedef std::map<std::string, NBNode*> NodeCont;
449 :
450 : /// @brief The map of names to nodes
451 : NodeCont myNodes;
452 :
453 : /// @brief The extracted nodes which are kept for reference
454 : NodeCont myExtractedNodes;
455 :
456 : /// @brief set of node ids which should not be joined
457 : std::set<std::string> myJoinExclusions;
458 :
459 : /// @brief loaded sets of node ids to join (cleared after use)
460 : std::vector<JoinCluster> myClusters2Join;
461 :
462 : /// @brief sets of node ids which were joined
463 : std::vector<std::set<std::string> > myJoinedClusters;
464 :
465 : /// @brief ids found in loaded join clusters used for error checking
466 : std::set<std::string> myJoined;
467 :
468 : /// @brief nodes that were created when splitting an edge
469 : std::set<const NBNode*> mySplit;
470 :
471 : /// @brief nodes that received a traffic light due to guessing (--tls.guess)
472 : std::set<NBNode*, ComparatorIdLess> myGuessedTLS;
473 :
474 : /// @brief nodes that are excluded from tls-guessing
475 : std::set<const NBNode*> myUnsetTLS;
476 :
477 : /// @brief node positions for faster lookup
478 : NamedRTree myRTree;
479 :
480 : /// @brief network components that must be removed if not connected to the road network via stop access
481 : std::vector<std::vector<std::string> > myRailComponents;
482 :
483 : /// @brief invalidated copy constructor
484 : NBNodeCont(const NBNodeCont& s) = delete;
485 :
486 : /// @brief invalidated assignment operator
487 : NBNodeCont& operator=(const NBNodeCont& s) = delete;
488 : };
|
