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