Use a queue to merge short roads, instead of a potentially quadratic scan.
-use std::collections::BTreeSet;
+use std::collections::{BTreeSet, VecDeque};
use geom::Distance;
use crate::osm::NodeID;
-use crate::raw::RawMap;
+use crate::raw::{OriginalRoad, RawMap};
// Manually adjust this to try locally. Need to work through issues with merging before enabling
// generally.
@@ -14,25 +14,30 @@ const SHORT_ROAD_THRESHOLD: Distance = Distance::const_meters(0.0);
pub fn merge_short_roads(map: &mut RawMap) -> BTreeSet<NodeID> {
let mut merged = BTreeSet::new();
- // An expensive fixed-point approach. When we merge one road, the IDs of some other roads might
- // change, so it's simplest just to start over.
- // TODO But since merge_short_road tells us what road IDs were deleted and created, it wouldn't
- // be hard to make a single pass.
- loop {
- let mut changes = false;
- for (id, road) in map.roads.clone() {
+ let mut queue: VecDeque<OriginalRoad> = VecDeque::new();
+ for r in map.roads.keys() {
+ queue.push_back(*r);
+ }
+
+ while !queue.is_empty() {
+ let id = queue.pop_front().unwrap();
+
+ // The road might've been deleted
+ if !map.roads.contains_key(&id) {
+ continue;
+ }
+
// See https://wiki.openstreetmap.org/wiki/Proposed_features/junction%3Dintersection
- if road.osm_tags.is("junction", "intersection")
+ if map.roads[&id].osm_tags.is("junction", "intersection")
|| map
.trimmed_road_geometry(id)
.map(|pl| pl.length() < SHORT_ROAD_THRESHOLD)
.unwrap_or(false)
{
match map.merge_short_road(id) {
- Ok((i, _, _, _)) => {
+ Ok((i, _, _, new_roads)) => {
merged.insert(i);
- changes = true;
- break;
+ queue.extend(new_roads);
}
Err(err) => {
warn!("Not merging short road / junction=intersection: {}", err);
@@ -40,10 +45,6 @@ pub fn merge_short_roads(map: &mut RawMap) -> BTreeSet<NodeID> {
}
}
}
- if !changes {
- break;
- }
- }
merged
}
