map_model/edits/
apply.rs

1use std::collections::{BTreeMap, BTreeSet, HashSet};
2
3use abstutil::Timer;
4use geom::{Distance, HashablePt2D, Line};
5use osm2streets::{osm, InputRoad};
6
7use crate::make::{match_points_to_lanes, snap_driveway, trim_path};
8use crate::{
9    connectivity, BuildingID, ControlStopSign, ControlTrafficSignal, EditCmd, EditEffects,
10    EditIntersectionControl, IntersectionControl, IntersectionID, LaneSpec, Map, MapEdits,
11    Movement, ParkingLotID, PathConstraints, Pathfinder, RoadID, Zone,
12};
13
14impl Map {
15    /// Returns (changed_roads, deleted_lanes, deleted_turns, added_turns, changed_intersections)
16    pub fn must_apply_edits(&mut self, new_edits: MapEdits, timer: &mut Timer) -> EditEffects {
17        self.apply_edits(new_edits, true, timer)
18    }
19
20    pub fn try_apply_edits(&mut self, new_edits: MapEdits, timer: &mut Timer) {
21        self.apply_edits(new_edits, false, timer);
22    }
23
24    /// Whatever edits have been applied, treat as the basemap. This erases all commands and
25    /// knowledge of what roads/intersections/etc looked like before.
26    pub fn treat_edits_as_basemap(&mut self) {
27        self.edits = self.new_edits();
28    }
29
30    // new_edits don't necessarily have to be valid; this could be used for speculatively testing
31    // edits. Doesn't update pathfinding yet.
32    fn apply_edits(
33        &mut self,
34        mut new_edits: MapEdits,
35        enforce_valid: bool,
36        timer: &mut Timer,
37    ) -> EditEffects {
38        self.edits_generation += 1;
39
40        let mut effects = EditEffects {
41            changed_roads: BTreeSet::new(),
42            deleted_lanes: BTreeSet::new(),
43            changed_intersections: BTreeSet::new(),
44            added_turns: BTreeSet::new(),
45            deleted_turns: BTreeSet::new(),
46            changed_parking_lots: BTreeSet::new(),
47            modified_lanes: BTreeSet::new(),
48        };
49
50        // Short-circuit to avoid marking pathfinder_dirty
51        if self.edits == new_edits {
52            return effects;
53        }
54
55        // We need to undo() all of the current commands in reverse order, then apply() all of the
56        // new commands. But in many cases, new_edits is just the current edits with a few commands
57        // at the end. So a simple optimization with equivalent behavior is to skip the common
58        // prefix of commands.
59        let mut start_at_idx = 0;
60        for (cmd1, cmd2) in self.edits.commands.iter().zip(new_edits.commands.iter()) {
61            if cmd1 == cmd2 {
62                start_at_idx += 1;
63            } else {
64                break;
65            }
66        }
67
68        timer.start_iter("undo old edits", self.edits.commands.len() - start_at_idx);
69        for _ in start_at_idx..self.edits.commands.len() {
70            timer.next();
71            self.edits
72                .commands
73                .pop()
74                .unwrap()
75                .undo()
76                .apply(&mut effects, self);
77        }
78
79        timer.start_iter("apply new edits", new_edits.commands.len() - start_at_idx);
80        for cmd in &new_edits.commands[start_at_idx..] {
81            timer.next();
82            cmd.apply(&mut effects, self);
83        }
84
85        timer.start("re-snap buildings");
86        let mut recalc_buildings = Vec::new();
87        for b in self.all_buildings() {
88            if effects.modified_lanes.contains(&b.sidewalk()) {
89                recalc_buildings.push(b.id);
90            }
91        }
92        fix_building_driveways(self, recalc_buildings, &mut effects);
93        timer.stop("re-snap buildings");
94
95        timer.start("re-snap parking lots");
96        let mut recalc_parking_lots = Vec::new();
97        for pl in self.all_parking_lots() {
98            if effects.modified_lanes.contains(&pl.driving_pos.lane())
99                || effects.modified_lanes.contains(&pl.sidewalk_pos.lane())
100            {
101                recalc_parking_lots.push(pl.id);
102                effects.changed_parking_lots.insert(pl.id);
103            }
104        }
105        fix_parking_lot_driveways(self, recalc_parking_lots);
106        timer.stop("re-snap parking lots");
107
108        // Might need to update bus stops.
109        if enforce_valid {
110            for id in &effects.changed_roads {
111                let stops = self.get_r(*id).transit_stops.clone();
112                for s in stops {
113                    let sidewalk_pos = self.get_ts(s).sidewalk_pos;
114                    // Must exist, because we aren't allowed to orphan a bus stop.
115                    let driving_lane = self
116                        .get_r(*id)
117                        .find_closest_lane(sidewalk_pos.lane(), |l| {
118                            PathConstraints::Bus.can_use(l, self)
119                        })
120                        .unwrap();
121                    let driving_pos = sidewalk_pos.equiv_pos(driving_lane, self);
122                    self.transit_stops.get_mut(&s).unwrap().driving_pos = driving_pos;
123                }
124            }
125        }
126
127        new_edits.update_derived(self);
128        self.edits = new_edits;
129        self.pathfinder_dirty = true;
130
131        if !effects.changed_roads.is_empty() {
132            self.zones = Zone::make_all(self);
133        }
134
135        // Some of these might've been added, then later deleted.
136        effects
137            .added_turns
138            .retain(|t| self.maybe_get_t(*t).is_some());
139
140        let mut more_changed_intersections = Vec::new();
141        for t in effects
142            .deleted_turns
143            .iter()
144            .chain(effects.added_turns.iter())
145        {
146            more_changed_intersections.push(t.parent);
147        }
148        effects
149            .changed_intersections
150            .extend(more_changed_intersections);
151
152        self.recalculate_road_to_buildings();
153
154        effects
155    }
156
157    /// This can expensive, so don't constantly do it while editing in the UI. But this must happen
158    /// before the simulation resumes.
159    pub fn recalculate_pathfinding_after_edits(&mut self, timer: &mut Timer) {
160        if !self.pathfinder_dirty {
161            return;
162        }
163
164        let mut pathfinder = std::mem::replace(&mut self.pathfinder, Pathfinder::empty());
165        pathfinder.apply_edits(self, timer);
166        self.pathfinder = pathfinder;
167
168        // Also recompute blackholes. This is cheap enough to do from scratch.
169        timer.start("recompute blackholes");
170        for road in &mut self.roads {
171            for lane in &mut road.lanes {
172                lane.driving_blackhole = false;
173                lane.biking_blackhole = false;
174            }
175        }
176        for l in connectivity::find_scc(self, PathConstraints::Car).1 {
177            self.mut_lane(l).driving_blackhole = true;
178        }
179        for l in connectivity::find_scc(self, PathConstraints::Bike).1 {
180            self.mut_lane(l).biking_blackhole = true;
181        }
182        timer.stop("recompute blackholes");
183
184        self.pathfinder_dirty = false;
185    }
186}
187
188impl EditCmd {
189    // Must be idempotent
190    fn apply(&self, effects: &mut EditEffects, map: &mut Map) {
191        match self {
192            EditCmd::ChangeRoad { r, ref new, .. } => {
193                let old_state = map.get_r_edit(*r);
194                if old_state == new.clone() {
195                    return;
196                }
197
198                if old_state.lanes_ltr != new.lanes_ltr {
199                    modify_lanes(map, *r, new.lanes_ltr.clone(), effects);
200                }
201                let road = &mut map.roads[r.0];
202                road.speed_limit = new.speed_limit;
203                road.access_restrictions = new.access_restrictions.clone();
204                road.modal_filter = new.modal_filter.clone();
205                road.crossings = new.crossings.clone();
206                road.turn_restrictions = new.turn_restrictions.clone();
207                road.complicated_turn_restrictions = new.complicated_turn_restrictions.clone();
208
209                effects.changed_roads.insert(road.id);
210                // TODO If lanes_ltr didn't change, can we skip some of this?
211                for i in [road.src_i, road.dst_i] {
212                    effects.changed_intersections.insert(i);
213                    let i = &mut map.intersections[i.0];
214                    i.outgoing_lanes.clear();
215                    i.incoming_lanes.clear();
216                    for r in &i.roads {
217                        for lane in &map.roads[r.0].lanes {
218                            if lane.src_i == i.id {
219                                i.outgoing_lanes.push(lane.id);
220                            } else {
221                                assert_eq!(lane.dst_i, i.id);
222                                i.incoming_lanes.push(lane.id);
223                            }
224                        }
225                    }
226
227                    recalculate_turns(i.id, map, effects);
228                }
229            }
230            EditCmd::ChangeIntersection {
231                i,
232                ref new,
233                ref old,
234            } => {
235                if map.get_i_edit(*i) == new.clone() {
236                    return;
237                }
238                map.intersections[i.0].modal_filter = new.modal_filter.clone();
239
240                map.stop_signs.remove(i);
241                map.traffic_signals.remove(i);
242                effects.changed_intersections.insert(*i);
243                match new.control {
244                    EditIntersectionControl::StopSign(ref ss) => {
245                        map.intersections[i.0].control = IntersectionControl::Signed;
246                        map.stop_signs.insert(*i, ss.clone());
247                    }
248                    EditIntersectionControl::TrafficSignal(ref raw_ts) => {
249                        map.intersections[i.0].control = IntersectionControl::Signalled;
250                        if old.control == EditIntersectionControl::Closed {
251                            recalculate_turns(*i, map, effects);
252                        }
253                        map.traffic_signals.insert(
254                            *i,
255                            ControlTrafficSignal::import(raw_ts.clone(), *i, map).unwrap(),
256                        );
257                    }
258                    EditIntersectionControl::Closed => {
259                        map.intersections[i.0].control = IntersectionControl::Construction;
260                    }
261                }
262
263                if old.control == EditIntersectionControl::Closed
264                    || new.control == EditIntersectionControl::Closed
265                {
266                    recalculate_turns(*i, map, effects);
267                }
268
269                for (turn, turn_type) in &new.crosswalks {
270                    map.mut_turn(*turn).turn_type = *turn_type;
271                }
272            }
273            EditCmd::ChangeRouteSchedule { id, new, .. } => {
274                map.transit_routes[id.0].spawn_times = new.clone();
275            }
276        }
277    }
278
279    fn undo(self) -> EditCmd {
280        match self {
281            EditCmd::ChangeRoad { r, old, new } => EditCmd::ChangeRoad {
282                r,
283                old: new,
284                new: old,
285            },
286            EditCmd::ChangeIntersection { i, old, new } => EditCmd::ChangeIntersection {
287                i,
288                old: new,
289                new: old,
290            },
291            EditCmd::ChangeRouteSchedule { id, old, new } => EditCmd::ChangeRouteSchedule {
292                id,
293                old: new,
294                new: old,
295            },
296        }
297    }
298}
299
300// This clobbers previously set traffic signal overrides.
301// TODO Step 1: Detect and warn about that
302// TODO Step 2: Avoid when possible
303fn recalculate_turns(id: IntersectionID, map: &mut Map, effects: &mut EditEffects) {
304    let i = &mut map.intersections[id.0];
305
306    if i.is_border() {
307        assert!(i.turns.is_empty());
308        return;
309    }
310
311    let mut old_turns = Vec::new();
312    for t in std::mem::take(&mut i.turns) {
313        effects.deleted_turns.insert(t.id);
314        old_turns.push(t);
315    }
316
317    if i.is_closed() {
318        return;
319    }
320
321    {
322        let turns = crate::make::turns::make_all_turns(map, map.get_i(id));
323        let i = &mut map.intersections[id.0];
324        for t in turns {
325            effects.added_turns.insert(t.id);
326            i.turns.push(t);
327        }
328    }
329    let movements = Movement::for_i(id, map);
330    let i = &mut map.intersections[id.0];
331    i.movements = movements;
332
333    match i.control {
334        IntersectionControl::Signed | IntersectionControl::Uncontrolled => {
335            // Stop sign policy usually doesn't depend on incoming lane types, except when changing
336            // to/from construction. To be safe, always regenerate. Edits to stop signs are rare
337            // anyway. And when we're smarter about preserving traffic signal changes in the face
338            // of lane changes, we can do the same here.
339            map.stop_signs.insert(id, ControlStopSign::new(map, id));
340        }
341        IntersectionControl::Signalled => {
342            map.traffic_signals
343                .insert(id, ControlTrafficSignal::new(map, id));
344        }
345        IntersectionControl::Construction => unreachable!(),
346    }
347}
348
349fn modify_lanes(map: &mut Map, r: RoadID, lanes_ltr: Vec<LaneSpec>, effects: &mut EditEffects) {
350    // First update intersection geometry and re-trim the road centers.
351    let mut road_geom_changed = Vec::new();
352    {
353        let road = map.get_r(r);
354        let (src_i, dst_i) = (road.src_i, road.dst_i);
355        let changed_road_width = lanes_ltr.iter().map(|spec| spec.width).sum();
356        road_geom_changed.extend(recalculate_intersection_polygon(
357            map,
358            r,
359            changed_road_width,
360            src_i,
361        ));
362        road_geom_changed.extend(recalculate_intersection_polygon(
363            map,
364            r,
365            changed_road_width,
366            dst_i,
367        ));
368    }
369
370    {
371        let road = &mut map.roads[r.0];
372        // TODO Revisit -- effects.deleted_lanes should probably totally go away. It is used below,
373        // though
374        for lane in &road.lanes {
375            effects.deleted_lanes.insert(lane.id);
376        }
377        road.recreate_lanes(lanes_ltr);
378    }
379
380    // We might've affected the geometry of other nearby roads.
381    for r in road_geom_changed {
382        effects.changed_roads.insert(r);
383        let lane_specs = map.get_r(r).lane_specs();
384        let road = &mut map.roads[r.0];
385        road.recreate_lanes(lane_specs);
386        for lane in &road.lanes {
387            effects.modified_lanes.insert(lane.id);
388        }
389    }
390    effects.modified_lanes.extend(effects.deleted_lanes.clone());
391}
392
393// Returns the other roads affected by this change, not counting changed_road.
394fn recalculate_intersection_polygon(
395    map: &mut Map,
396    changed_road: RoadID,
397    changed_road_width: Distance,
398    i: IntersectionID,
399) -> Vec<RoadID> {
400    let intersection = map.get_i(i);
401
402    let mut input_roads = Vec::new();
403    for r in &intersection.roads {
404        let r = map.get_r(*r);
405
406        let total_width = if r.id == changed_road {
407            changed_road_width
408        } else {
409            r.get_width()
410        };
411
412        input_roads.push(InputRoad {
413            // Just map our IDs to something in osm2streets ID space.
414            id: osm2streets::RoadID(r.id.0),
415            src_i: osm2streets::IntersectionID(r.src_i.0),
416            dst_i: osm2streets::IntersectionID(r.dst_i.0),
417            center_line: r.untrimmed_center_pts.clone(),
418            total_width,
419            highway_type: r
420                .osm_tags
421                .get(osm::HIGHWAY)
422                .or_else(|| r.osm_tags.get("railway"))
423                .unwrap()
424                .to_string(),
425        });
426    }
427
428    let results = match osm2streets::intersection_polygon(
429        osm2streets::IntersectionID(intersection.id.0),
430        input_roads,
431        // For consolidated intersections, it appears we don't need to pass in
432        // trim_roads_for_merging. May revisit this later if needed.
433        &BTreeMap::new(),
434    ) {
435        Ok(results) => results,
436        Err(err) => {
437            error!("Couldn't recalculate {i}'s geometry: {err}");
438            return Vec::new();
439        }
440    };
441
442    map.intersections[i.0].polygon = results.intersection_polygon;
443
444    // Recalculate trimmed centers
445    let mut affected = Vec::new();
446    for (id, dist) in results.trim_starts {
447        let id = RoadID(id.0);
448        let road = &mut map.roads[id.0];
449        road.trim_start = dist;
450        if let Some(pl) = osm2streets::Road::trim_polyline_both_ends(
451            road.untrimmed_center_pts.clone(),
452            road.trim_start,
453            road.trim_end,
454        ) {
455            road.center_pts = pl;
456        } else {
457            // If the road geometrically vanishes, don't do anything for now
458            error!("{} on trim_start broke", road.id);
459        }
460        if id != changed_road {
461            affected.push(id);
462        }
463    }
464    for (id, dist) in results.trim_ends {
465        let id = RoadID(id.0);
466        let road = &mut map.roads[id.0];
467        road.trim_end = dist;
468        if let Some(pl) = osm2streets::Road::trim_polyline_both_ends(
469            road.untrimmed_center_pts.clone(),
470            road.trim_start,
471            road.trim_end,
472        ) {
473            road.center_pts = pl;
474        } else {
475            error!("{} on trim_end broke", road.id);
476        }
477        if id != changed_road {
478            affected.push(id);
479        }
480    }
481    affected
482}
483
484/// Recalculate the driveways of some buildings after map edits.
485fn fix_building_driveways(map: &mut Map, input: Vec<BuildingID>, effects: &mut EditEffects) {
486    // TODO Copying from make/buildings.rs
487    let mut center_per_bldg: BTreeMap<BuildingID, HashablePt2D> = BTreeMap::new();
488    let mut query: HashSet<HashablePt2D> = HashSet::new();
489    for id in input {
490        let center = map.get_b(id).polygon.center().to_hashable();
491        center_per_bldg.insert(id, center);
492        query.insert(center);
493    }
494
495    let sidewalk_buffer = Distance::meters(7.5);
496    let mut sidewalk_pts = match_points_to_lanes(
497        map,
498        query,
499        |l| l.is_walkable(),
500        // Don't put connections too close to intersections
501        sidewalk_buffer,
502        // Try not to skip any buildings, but more than 1km from a sidewalk is a little much
503        Distance::meters(1000.0),
504        &mut Timer::throwaway(),
505    );
506
507    for (id, bldg_center) in center_per_bldg {
508        match sidewalk_pts.remove(&bldg_center).and_then(|pos| {
509            Line::new(bldg_center.to_pt2d(), pos.pt(map))
510                .map(|l| (pos, trim_path(&map.get_b(id).polygon, l)))
511                .ok()
512        }) {
513            Some((sidewalk_pos, driveway_geom)) => {
514                let b = &mut map.buildings[id.0];
515                b.sidewalk_pos = sidewalk_pos;
516                b.driveway_geom = driveway_geom.to_polyline();
517                // We may need to redraw the road that now has this building snapped to it
518                effects.changed_roads.insert(sidewalk_pos.lane().road);
519            }
520            None => {
521                // TODO Not sure what to do here yet.
522                error!("{} isn't snapped to a sidewalk now!", id);
523            }
524        }
525    }
526}
527
528/// Recalculate the driveways of some parking lots after map edits.
529fn fix_parking_lot_driveways(map: &mut Map, input: Vec<ParkingLotID>) {
530    // TODO Partly copying from make/parking_lots.rs
531    let mut center_per_lot: Vec<(ParkingLotID, HashablePt2D)> = Vec::new();
532    let mut query: HashSet<HashablePt2D> = HashSet::new();
533    for id in input {
534        let center = map.get_pl(id).polygon.center().to_hashable();
535        center_per_lot.push((id, center));
536        query.insert(center);
537    }
538
539    let sidewalk_buffer = Distance::meters(7.5);
540    let sidewalk_pts = match_points_to_lanes(
541        map,
542        query,
543        |l| l.is_walkable(),
544        sidewalk_buffer,
545        Distance::meters(1000.0),
546        &mut Timer::throwaway(),
547    );
548
549    for (id, center) in center_per_lot {
550        match snap_driveway(center, &map.get_pl(id).polygon, &sidewalk_pts, map) {
551            Ok((driveway_line, driving_pos, sidewalk_line, sidewalk_pos)) => {
552                let pl = &mut map.parking_lots[id.0];
553                pl.driveway_line = driveway_line;
554                pl.driving_pos = driving_pos;
555                pl.sidewalk_line = sidewalk_line;
556                pl.sidewalk_pos = sidewalk_pos;
557            }
558            Err(err) => {
559                // TODO Not sure what to do here yet.
560                error!("{} isn't snapped to a sidewalk now: {}", id, err);
561            }
562        }
563    }
564}