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 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 pub fn treat_edits_as_basemap(&mut self) {
27 self.edits = self.new_edits();
28 }
29
30 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 if self.edits == new_edits {
52 return effects;
53 }
54
55 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 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 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 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 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 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 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 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
300fn 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 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 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 for lane in &road.lanes {
375 effects.deleted_lanes.insert(lane.id);
376 }
377 road.recreate_lanes(lanes_ltr);
378 }
379
380 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
393fn 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 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 &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 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 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
484fn fix_building_driveways(map: &mut Map, input: Vec<BuildingID>, effects: &mut EditEffects) {
486 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 sidewalk_buffer,
502 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 effects.changed_roads.insert(sidewalk_pos.lane().road);
519 }
520 None => {
521 error!("{} isn't snapped to a sidewalk now!", id);
523 }
524 }
525 }
526}
527
528fn fix_parking_lot_driveways(map: &mut Map, input: Vec<ParkingLotID>) {
530 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 error!("{} isn't snapped to a sidewalk now: {}", id, err);
561 }
562 }
563 }
564}