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