map_model/
map.rs

1//! A bunch of (mostly read-only) queries on a Map.
2
3use std::{
4    collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque},
5    sync::{Arc, RwLock},
6};
7
8use anyhow::{Context, Result};
9use petgraph::graphmap::{DiGraphMap, UnGraphMap};
10use popgetter::CensusZone;
11
12use abstio::{CityName, MapName};
13use abstutil::{prettyprint_usize, serialized_size_bytes, MultiMap, Tags, Timer};
14use geom::{
15    Angle, Bounds, Distance, Duration, FindClosest, GPSBounds, LonLat, PolyLine, Polygon, Pt2D,
16    Ring, Time,
17};
18use raw_map::{RawBuilding, RawMap};
19
20use crate::{
21    osm, AmenityType, Area, AreaID, AreaType, Building, BuildingID, BuildingType, CommonEndpoint,
22    CompressedMovementID, ControlStopSign, ControlTrafficSignal, DirectedRoadID, Direction,
23    DrivingSide, ExtraPOI, Intersection, IntersectionControl, IntersectionID, IntersectionKind,
24    Lane, LaneID, LaneType, Map, MapConfig, MapEdits, Movement, MovementID, OffstreetParking,
25    OriginalRoad, ParkingLot, ParkingLotID, Path, PathConstraints, PathRequest, PathV2, Pathfinder,
26    PathfinderCaching, Position, Road, RoadFilter, RoadID, RoutingParams, TransitRoute,
27    TransitRouteID, TransitStop, TransitStopID, Turn, TurnID, TurnType, Zone,
28};
29
30impl Map {
31    /// Load a map from a local serialized Map or RawMap. Note this won't work on web. This should
32    /// only be used by non-UI tools.
33    pub fn load_synchronously(path: String, timer: &mut Timer) -> Map {
34        if path.contains("/maps/") {
35            match abstio::maybe_read_binary(path.clone(), timer) {
36                Ok(map) => {
37                    let mut map: Map = map;
38                    map.map_loaded_directly(timer);
39                    return map;
40                }
41                Err(err) => {
42                    error!("\nError loading {}: {}\n", path, err);
43                    if err.to_string().contains("No such file") {
44                        error!(
45                            "{} is missing. You may need to do: cargo run --bin updater",
46                            path
47                        );
48                    } else {
49                        error!(
50                            "{} is out-of-date. You may need to update your build (git pull) or \
51                             download new data (cargo run --bin updater). If this is a custom \
52                             map, you need to import it again.",
53                            path
54                        );
55                    }
56                    error!(
57                        "Check https://a-b-street.github.io/docs/tech/dev/index.html and file an issue \
58                         if you have trouble."
59                    );
60
61                    std::process::exit(1);
62                }
63            }
64        }
65
66        let raw: RawMap = abstio::read_binary(path, timer);
67        Map::create_from_raw(raw, crate::RawToMapOptions::default(), timer)
68    }
69
70    /// After deserializing a map directly, call this after.
71    pub fn map_loaded_directly(&mut self, timer: &mut Timer) {
72        #![allow(clippy::logic_bug)]
73        // For debugging map file sizes
74
75        self.edits = self.new_edits();
76        self.recalculate_road_to_buildings();
77        self.recalculate_all_movements(timer);
78
79        // Enable to work on shrinking map file sizes. Never run this on the web though --
80        // trying to serialize fast_paths in wasm melts the browser, because the usize<->u32
81        // translation there isn't meant to run on wasm.
82        if cfg!(not(target_arch = "wasm32")) && false {
83            let mut costs = vec![
84                (
85                    "roads",
86                    self.roads.len(),
87                    serialized_size_bytes(&self.roads),
88                ),
89                (
90                    "intersections",
91                    self.intersections.len(),
92                    serialized_size_bytes(&self.intersections),
93                ),
94                (
95                    "buildings",
96                    self.buildings.len(),
97                    serialized_size_bytes(&self.buildings),
98                ),
99                (
100                    "areas",
101                    self.areas.len(),
102                    serialized_size_bytes(&self.areas),
103                ),
104                (
105                    "parking lots",
106                    self.parking_lots.len(),
107                    serialized_size_bytes(&self.parking_lots),
108                ),
109                (
110                    "zones",
111                    self.zones.len(),
112                    serialized_size_bytes(&self.zones),
113                ),
114                (
115                    "census_zones",
116                    self.census_zones.len(),
117                    serialized_size_bytes(&self.census_zones),
118                ),
119                (
120                    "extra_pois",
121                    self.extra_pois.len(),
122                    serialized_size_bytes(&self.extra_pois),
123                ),
124                ("pathfinder", 1, serialized_size_bytes(&self.pathfinder)),
125            ];
126            costs.sort_by_key(|(_, _, bytes)| *bytes);
127            costs.reverse();
128
129            info!(
130                "Total map size: {} bytes",
131                prettyprint_usize(serialized_size_bytes(self))
132            );
133            for (name, number, bytes) in costs {
134                info!(
135                    "- {} {}: {} bytes",
136                    prettyprint_usize(number),
137                    name,
138                    prettyprint_usize(bytes)
139                );
140            }
141        }
142    }
143
144    /// Just for temporary std::mem::replace tricks.
145    pub fn blank() -> Map {
146        Map {
147            roads: Vec::new(),
148            intersections: Vec::new(),
149            intersection_quad_tree: Arc::new(RwLock::new(None)),
150            buildings: Vec::new(),
151            transit_stops: BTreeMap::new(),
152            transit_routes: Vec::new(),
153            areas: Vec::new(),
154            parking_lots: Vec::new(),
155            zones: Vec::new(),
156            census_zones: Vec::new(),
157            extra_pois: Vec::new(),
158            boundary_polygon: Ring::must_new(vec![
159                Pt2D::new(0.0, 0.0),
160                Pt2D::new(1.0, 0.0),
161                Pt2D::new(1.0, 1.0),
162                Pt2D::new(0.0, 0.0),
163            ])
164            .into_polygon(),
165            stop_signs: BTreeMap::new(),
166            traffic_signals: BTreeMap::new(),
167            bus_routes_on_roads: MultiMap::new(),
168            gps_bounds: GPSBounds::new(),
169            bounds: Bounds::new(),
170            config: MapConfig::default(),
171            pathfinder: Pathfinder::empty(),
172            pathfinder_dirty: false,
173            routing_params: RoutingParams::default(),
174            name: MapName::blank(),
175            edits: MapEdits::new(),
176            edits_generation: 0,
177            road_to_buildings: MultiMap::new(),
178        }
179    }
180
181    /// A dummy map that won't crash UIs, but has almost nothing in it.
182    pub fn almost_blank() -> Self {
183        // Programatically creating a Map is very verbose. RawMap less so, but .osm could be even
184        // better... but then we'd pull in dependencies for XML parsing everywhere.
185        let mut raw = RawMap::blank(MapName::blank());
186
187        raw.streets.boundary_polygon = Polygon::rectangle(100.0, 100.0);
188        raw.streets
189            .gps_bounds
190            .update(LonLat::new(-122.453224, 47.723277));
191        raw.streets
192            .gps_bounds
193            .update(LonLat::new(-122.240505, 47.495342));
194
195        let i1 = raw.streets.insert_intersection(
196            Vec::new(),
197            Pt2D::new(30.0, 30.0),
198            IntersectionKind::MapEdge,
199            IntersectionControl::Uncontrolled,
200        );
201        let i2 = raw.streets.insert_intersection(
202            Vec::new(),
203            Pt2D::new(70.0, 70.0),
204            IntersectionKind::MapEdge,
205            IntersectionControl::Uncontrolled,
206        );
207        raw.elevation_per_intersection.insert(i1, Distance::ZERO);
208        raw.elevation_per_intersection.insert(i2, Distance::ZERO);
209
210        let mut tags = Tags::empty();
211        tags.insert("highway", "residential");
212        tags.insert("lanes", "2");
213        let road_id = raw.streets.next_road_id();
214        raw.streets.insert_road(osm2streets::Road::new(
215            road_id,
216            Vec::new(),
217            i1,
218            i2,
219            PolyLine::must_new(vec![Pt2D::new(30.0, 30.0), Pt2D::new(70.0, 70.0)]),
220            tags,
221            &raw.streets.config,
222        ));
223        raw.extra_road_data
224            .insert(road_id, raw_map::ExtraRoadData::default());
225
226        raw.buildings.insert(
227            osm::OsmID::Way(osm::WayID(3)),
228            RawBuilding {
229                polygon: Polygon::rectangle_centered(
230                    Pt2D::new(50.0, 20.0),
231                    Distance::meters(30.0),
232                    Distance::meters(10.0),
233                ),
234                osm_tags: Tags::empty(),
235                public_garage_name: None,
236                num_parking_spots: 0,
237                amenities: Vec::new(),
238            },
239        );
240
241        Self::create_from_raw(
242            raw,
243            crate::RawToMapOptions::default(),
244            &mut Timer::throwaway(),
245        )
246    }
247
248    pub fn all_roads(&self) -> &Vec<Road> {
249        &self.roads
250    }
251
252    pub fn all_roads_with_modal_filter(&self) -> impl Iterator<Item = (&Road, &RoadFilter)> {
253        self.roads.iter().filter_map(|r| {
254            if let Some(ref filter) = r.modal_filter {
255                Some((r, filter))
256            } else {
257                None
258            }
259        })
260    }
261
262    pub fn all_lanes(&self) -> impl Iterator<Item = &Lane> {
263        self.roads.iter().flat_map(|r| r.lanes.iter())
264    }
265
266    pub fn all_intersections(&self) -> &Vec<Intersection> {
267        &self.intersections
268    }
269
270    pub fn all_turns(&self) -> impl Iterator<Item = &Turn> {
271        self.intersections.iter().flat_map(|i| i.turns.iter())
272    }
273
274    pub fn all_buildings(&self) -> &Vec<Building> {
275        &self.buildings
276    }
277
278    pub fn all_areas(&self) -> &Vec<Area> {
279        &self.areas
280    }
281
282    pub fn all_parking_lots(&self) -> &Vec<ParkingLot> {
283        &self.parking_lots
284    }
285
286    pub fn all_zones(&self) -> &Vec<Zone> {
287        &self.zones
288    }
289
290    pub fn all_census_zones(&self) -> &Vec<(Polygon, CensusZone)> {
291        &self.census_zones
292    }
293
294    pub fn all_extra_pois(&self) -> &Vec<ExtraPOI> {
295        &self.extra_pois
296    }
297
298    pub fn maybe_get_r(&self, id: RoadID) -> Option<&Road> {
299        self.roads.get(id.0)
300    }
301
302    pub fn maybe_get_l(&self, id: LaneID) -> Option<&Lane> {
303        self.maybe_get_r(id.road)?.lanes.get(id.offset)
304    }
305
306    pub fn maybe_get_i(&self, id: IntersectionID) -> Option<&Intersection> {
307        self.intersections.get(id.0)
308    }
309
310    pub fn maybe_get_t(&self, id: TurnID) -> Option<&Turn> {
311        // Looking up the intersection is fast. Linearly scanning through all of the turns to find
312        // this one actually turns out to be fast too; thanks cache locality.
313        for turn in &self.intersections[id.parent.0].turns {
314            if turn.id == id {
315                return Some(turn);
316            }
317        }
318        None
319    }
320
321    pub fn maybe_get_b(&self, id: BuildingID) -> Option<&Building> {
322        self.buildings.get(id.0)
323    }
324
325    pub fn maybe_get_pl(&self, id: ParkingLotID) -> Option<&ParkingLot> {
326        self.parking_lots.get(id.0)
327    }
328
329    pub fn maybe_get_a(&self, id: AreaID) -> Option<&Area> {
330        self.areas.get(id.0)
331    }
332
333    pub fn maybe_get_ts(&self, id: TransitStopID) -> Option<&TransitStop> {
334        self.transit_stops.get(&id)
335    }
336
337    pub fn maybe_get_stop_sign(&self, id: IntersectionID) -> Option<&ControlStopSign> {
338        self.stop_signs.get(&id)
339    }
340
341    pub fn maybe_get_traffic_signal(&self, id: IntersectionID) -> Option<&ControlTrafficSignal> {
342        self.traffic_signals.get(&id)
343    }
344
345    pub fn maybe_get_tr(&self, route: TransitRouteID) -> Option<&TransitRoute> {
346        self.transit_routes.get(route.0)
347    }
348
349    pub fn get_r(&self, id: RoadID) -> &Road {
350        &self.roads[id.0]
351    }
352
353    pub fn get_l(&self, id: LaneID) -> &Lane {
354        &self.roads[id.road.0].lanes[id.offset]
355    }
356
357    pub(crate) fn mut_lane(&mut self, id: LaneID) -> &mut Lane {
358        &mut self.roads[id.road.0].lanes[id.offset]
359    }
360    /// Public for importer. Do not abuse!
361    pub fn mut_road(&mut self, id: RoadID) -> &mut Road {
362        &mut self.roads[id.0]
363    }
364    pub(crate) fn mut_turn(&mut self, id: TurnID) -> &mut Turn {
365        for turn in &mut self.intersections[id.parent.0].turns {
366            if turn.id == id {
367                return turn;
368            }
369        }
370        panic!("Couldn't find {id}");
371    }
372
373    pub fn get_i(&self, id: IntersectionID) -> &Intersection {
374        &self.intersections[id.0]
375    }
376
377    pub fn get_t(&self, id: TurnID) -> &Turn {
378        // When pathfinding breaks, seeing this TurnID is useful.
379        if let Some(turn) = self.maybe_get_t(id) {
380            turn
381        } else {
382            panic!("Can't get_t({})", id);
383        }
384    }
385
386    pub fn get_b(&self, id: BuildingID) -> &Building {
387        &self.buildings[id.0]
388    }
389
390    pub fn get_a(&self, id: AreaID) -> &Area {
391        &self.areas[id.0]
392    }
393
394    pub fn get_pl(&self, id: ParkingLotID) -> &ParkingLot {
395        &self.parking_lots[id.0]
396    }
397
398    pub fn get_stop_sign(&self, id: IntersectionID) -> &ControlStopSign {
399        &self.stop_signs[&id]
400    }
401
402    pub fn get_traffic_signal(&self, id: IntersectionID) -> &ControlTrafficSignal {
403        &self.traffic_signals[&id]
404    }
405
406    /// This will return None for SharedSidewalkCorners
407    pub fn get_movement(&self, id: MovementID) -> Option<&Movement> {
408        self.get_i(id.parent).movements.get(&id)
409    }
410
411    // All these helpers should take IDs and return objects.
412
413    /// The turns may belong to two different intersections!
414    pub fn get_turns_from_lane(&self, l: LaneID) -> Vec<&Turn> {
415        let lane = self.get_l(l);
416        self.get_i(lane.dst_i)
417            .turns
418            .iter()
419            // Sidewalks are bidirectional, so include turns from the source intersection
420            .chain(
421                self.get_i(lane.src_i)
422                    .turns
423                    .iter()
424                    // And then don't yield them if this isn't a sidewalk
425                    .take_while(|_| lane.is_walkable()),
426            )
427            .filter(|t| t.id.src == l || (lane.is_walkable() && t.id.dst == l))
428            .collect()
429    }
430
431    pub fn get_turns_to_lane(&self, l: LaneID) -> Vec<&Turn> {
432        let lane = self.get_l(l);
433
434        // Sidewalks/shoulders are bidirectional
435        if lane.is_walkable() {
436            return self.get_turns_from_lane(l);
437        }
438
439        let turns: Vec<&Turn> = self
440            .get_i(lane.src_i)
441            .turns
442            .iter()
443            .filter(|t| t.id.dst == l)
444            .collect();
445        turns
446    }
447
448    pub fn get_turn_between(
449        &self,
450        from: LaneID,
451        to: LaneID,
452        parent: IntersectionID,
453    ) -> Option<&Turn> {
454        self.get_i(parent)
455            .turns
456            .iter()
457            .find(|t| t.id.src == from && t.id.dst == to)
458    }
459
460    pub fn get_next_turns_and_lanes(&self, from: LaneID) -> Vec<(&Turn, &Lane)> {
461        self.get_turns_from_lane(from)
462            .into_iter()
463            .map(|t| {
464                (
465                    t,
466                    self.get_l(if t.id.src == from { t.id.dst } else { t.id.src }),
467                )
468            })
469            .collect()
470    }
471
472    pub fn get_next_turns_and_lanes_for(
473        &self,
474        from: LaneID,
475        constraints: PathConstraints,
476    ) -> Vec<(&Turn, &Lane)> {
477        self.get_next_turns_and_lanes(from)
478            .into_iter()
479            .filter(|(_, l)| constraints.can_use(l, self))
480            .collect()
481    }
482
483    pub fn get_turns_for(&self, from: LaneID, constraints: PathConstraints) -> Vec<&Turn> {
484        self.get_next_turns_and_lanes_for(from, constraints)
485            .into_iter()
486            .map(|(t, _)| t)
487            .collect()
488    }
489
490    /// Find all movements from one road to another that're usable by someone.
491    pub fn get_movements_for(
492        &self,
493        from: DirectedRoadID,
494        constraints: PathConstraints,
495    ) -> Vec<MovementID> {
496        let mut result = BTreeSet::new();
497        for t in &self.get_i(from.dst_i(self)).turns {
498            let src = self.get_l(t.id.src);
499            if src.get_directed_parent() == from
500                && constraints.can_use(src, self)
501                && constraints.can_use(self.get_l(t.id.dst), self)
502            {
503                result.insert(t.id.to_movement(self));
504            }
505        }
506        // TODO Sidewalks are bidirectional
507        assert!(constraints != PathConstraints::Pedestrian);
508        result.into_iter().collect()
509    }
510
511    pub fn get_next_roads(&self, from: RoadID) -> BTreeSet<RoadID> {
512        let mut roads: BTreeSet<RoadID> = BTreeSet::new();
513        let r = self.get_r(from);
514        for id in vec![r.src_i, r.dst_i].into_iter() {
515            roads.extend(self.get_i(id).roads.clone());
516        }
517        roads
518    }
519
520    pub fn get_parent(&self, id: LaneID) -> &Road {
521        self.get_r(id.road)
522    }
523
524    pub fn get_gps_bounds(&self) -> &GPSBounds {
525        &self.gps_bounds
526    }
527
528    pub fn get_bounds(&self) -> &Bounds {
529        &self.bounds
530    }
531
532    pub fn get_city_name(&self) -> &CityName {
533        &self.name.city
534    }
535
536    pub fn get_name(&self) -> &MapName {
537        &self.name
538    }
539
540    pub fn all_transit_stops(&self) -> &BTreeMap<TransitStopID, TransitStop> {
541        &self.transit_stops
542    }
543
544    pub fn get_ts(&self, stop: TransitStopID) -> &TransitStop {
545        &self.transit_stops[&stop]
546    }
547
548    pub fn get_tr(&self, route: TransitRouteID) -> &TransitRoute {
549        &self.transit_routes[route.0]
550    }
551
552    pub fn all_transit_routes(&self) -> &Vec<TransitRoute> {
553        &self.transit_routes
554    }
555
556    pub fn get_transit_route(&self, name: &str) -> Option<&TransitRoute> {
557        self.transit_routes.iter().find(|r| r.long_name == name)
558    }
559
560    pub fn get_routes_serving_stop(&self, stop: TransitStopID) -> Vec<&TransitRoute> {
561        let mut routes = Vec::new();
562        for r in &self.transit_routes {
563            if r.stops.contains(&stop) {
564                routes.push(r);
565            }
566        }
567        routes
568    }
569
570    pub fn building_to_road(&self, id: BuildingID) -> &Road {
571        self.get_parent(self.get_b(id).sidewalk())
572    }
573
574    /// This and all_outgoing_borders are expensive to constantly repeat
575    pub fn all_incoming_borders(&self) -> Vec<&Intersection> {
576        let mut result: Vec<&Intersection> = Vec::new();
577        for i in &self.intersections {
578            if i.is_incoming_border() {
579                result.push(i);
580            }
581        }
582        result
583    }
584
585    pub fn all_outgoing_borders(&self) -> Vec<&Intersection> {
586        let mut result: Vec<&Intersection> = Vec::new();
587        for i in &self.intersections {
588            if i.is_outgoing_border() {
589                result.push(i);
590            }
591        }
592        result
593    }
594
595    pub fn save(&self) {
596        assert!(self.edits.edits_name.starts_with("Untitled Proposal"));
597        assert!(self.edits.commands.is_empty());
598        assert!(!self.pathfinder_dirty);
599        abstio::write_binary(self.name.path(), self);
600    }
601
602    /// Cars trying to park near this building should head for the driving lane returned here, then
603    /// start their search. Some parking lanes are connected to driving lanes that're "parking
604    /// blackholes" -- if there are no free spots on that lane, then the roads force cars to a
605    /// border.
606    // TODO Making driving_connection do this.
607    pub fn find_driving_lane_near_building(&self, b: BuildingID) -> LaneID {
608        let sidewalk = self.get_b(b).sidewalk();
609        if let Some(l) = self
610            .get_parent(sidewalk)
611            .find_closest_lane(sidewalk, |l| PathConstraints::Car.can_use(l, self))
612        {
613            if !self.get_l(l).driving_blackhole {
614                return l;
615            }
616        }
617
618        let mut roads_queue: VecDeque<RoadID> = VecDeque::new();
619        let mut visited: HashSet<RoadID> = HashSet::new();
620        {
621            let start = self.building_to_road(b).id;
622            roads_queue.push_back(start);
623            visited.insert(start);
624        }
625
626        loop {
627            if roads_queue.is_empty() {
628                panic!(
629                    "Giving up looking for a driving lane near {}, searched {} roads: {:?}",
630                    b,
631                    visited.len(),
632                    visited
633                );
634            }
635            let r = self.get_r(roads_queue.pop_front().unwrap());
636
637            for (l, lt) in r
638                .children_forwards()
639                .into_iter()
640                .chain(r.children_backwards().into_iter())
641            {
642                if lt == LaneType::Driving && !self.get_l(l).driving_blackhole {
643                    return l;
644                }
645            }
646
647            for next_r in self.get_next_roads(r.id).into_iter() {
648                if !visited.contains(&next_r) {
649                    roads_queue.push_back(next_r);
650                    visited.insert(next_r);
651                }
652            }
653        }
654    }
655
656    pub fn get_boundary_polygon(&self) -> &Polygon {
657        &self.boundary_polygon
658    }
659
660    pub fn get_pathfinder(&self) -> &Pathfinder {
661        &self.pathfinder
662    }
663
664    pub fn pathfind(&self, req: PathRequest) -> Result<Path> {
665        self.pathfind_v2(req)?.into_v1(self)
666    }
667    pub fn pathfind_with_params(
668        &self,
669        req: PathRequest,
670        params: &RoutingParams,
671        cache_custom: PathfinderCaching,
672    ) -> Result<Path> {
673        self.pathfind_v2_with_params(req, params, cache_custom)?
674            .into_v1(self)
675    }
676    pub fn pathfind_v2(&self, req: PathRequest) -> Result<PathV2> {
677        assert!(!self.pathfinder_dirty);
678        self.pathfinder
679            .pathfind(req.clone(), self)
680            .ok_or_else(|| anyhow!("can't fulfill {}", req))
681    }
682    pub fn pathfind_v2_with_params(
683        &self,
684        req: PathRequest,
685        params: &RoutingParams,
686        cache_custom: PathfinderCaching,
687    ) -> Result<PathV2> {
688        assert!(!self.pathfinder_dirty);
689        self.pathfinder
690            .pathfind_with_params(req.clone(), params, cache_custom, self)
691            .ok_or_else(|| anyhow!("can't fulfill {}", req))
692    }
693    pub fn should_use_transit(
694        &self,
695        start: Position,
696        end: Position,
697    ) -> Option<(TransitStopID, Option<TransitStopID>, TransitRouteID)> {
698        assert!(!self.pathfinder_dirty);
699        self.pathfinder.should_use_transit(self, start, end)
700    }
701
702    /// Return the cost of a single path, and also a mapping from every directed road to the cost
703    /// of getting there from the same start. This can be used to understand why an alternative
704    /// route wasn't chosen.
705    pub fn all_costs_from(
706        &self,
707        req: PathRequest,
708    ) -> Option<(Duration, HashMap<DirectedRoadID, Duration>)> {
709        assert!(!self.pathfinder_dirty);
710        self.pathfinder.all_costs_from(req, self)
711    }
712
713    /// None for SharedSidewalkCorners and turns not belonging to traffic signals
714    pub fn get_movement_for_traffic_signal(
715        &self,
716        t: TurnID,
717    ) -> Option<(MovementID, CompressedMovementID)> {
718        let i = self.get_i(t.parent);
719        if !i.is_traffic_signal() || self.get_t(t).turn_type == TurnType::SharedSidewalkCorner {
720            return None;
721        }
722        Some(i.turn_to_movement(t))
723    }
724
725    pub fn find_r_by_osm_id(&self, id: OriginalRoad) -> Result<RoadID> {
726        for r in self.all_roads() {
727            if r.orig_id == id {
728                return Ok(r.id);
729            }
730        }
731        bail!("Can't find {}", id)
732    }
733
734    pub fn find_i_by_osm_id(&self, id: osm::NodeID) -> Result<IntersectionID> {
735        for i in self.all_intersections() {
736            if i.orig_id == id {
737                return Ok(i.id);
738            }
739        }
740        bail!("Can't find {}", id)
741    }
742
743    fn populate_intersection_quad_tree(&self) {
744        let quad_tree_lock = Arc::clone(&self.intersection_quad_tree);
745        let mut quad_tree = quad_tree_lock.write().unwrap();
746
747        if quad_tree.is_some() {
748            return;
749        }
750
751        let mut quad: FindClosest<IntersectionID> = FindClosest::new();
752
753        for intersection in self.all_intersections() {
754            quad.add_polygon(intersection.id, &intersection.polygon);
755        }
756        *quad_tree = Some(quad);
757    }
758
759    pub fn localise_lon_lat_to_map(&self, point: LonLat) -> Pt2D {
760        point.to_pt(&self.gps_bounds)
761    }
762
763    pub fn find_i_by_pt2d(&self, pnt: Pt2D) -> Result<IntersectionID> {
764        self.populate_intersection_quad_tree();
765        let quad_tree_lock = Arc::clone(&self.intersection_quad_tree);
766        let quad_tree = quad_tree_lock.read().unwrap();
767
768        if let Some(tree) = &*quad_tree {
769            let (intersection_id, _) = tree
770                .closest_pt(pnt, Distance::meters(100.0))
771                .context("Failed to find intersection within 100m of specified point")?;
772            Ok(intersection_id)
773        } else {
774            unreachable!("Intersection Quad tree was somehow blank even after generation")
775        }
776    }
777
778    pub fn find_b_by_osm_id(&self, id: osm::OsmID) -> Option<BuildingID> {
779        for b in self.all_buildings() {
780            if b.orig_id == id {
781                return Some(b.id);
782            }
783        }
784        None
785    }
786
787    pub fn find_tr_by_gtfs(&self, gtfs_id: &str) -> Option<TransitRouteID> {
788        for tr in self.all_transit_routes() {
789            if tr.gtfs_id == gtfs_id {
790                return Some(tr.id);
791            }
792        }
793        None
794    }
795
796    // TODO Sort of a temporary hack
797    pub fn hack_override_offstreet_spots(&mut self, spots_per_bldg: usize) {
798        for b in &mut self.buildings {
799            if let OffstreetParking::Private(ref mut num_spots, _) = b.parking {
800                *num_spots = spots_per_bldg;
801            }
802        }
803    }
804    pub fn hack_override_offstreet_spots_individ(&mut self, b: BuildingID, spots: usize) {
805        let b = &mut self.buildings[b.0];
806        if let OffstreetParking::Private(ref mut num_spots, _) = b.parking {
807            *num_spots = spots;
808        }
809    }
810
811    pub fn hack_override_bldg_type(&mut self, b: BuildingID, bldg_type: BuildingType) {
812        self.buildings[b.0].bldg_type = bldg_type;
813    }
814
815    pub fn hack_override_orig_spawn_times(&mut self, br: TransitRouteID, times: Vec<Time>) {
816        self.transit_routes[br.0].orig_spawn_times = times.clone();
817        self.transit_routes[br.0].spawn_times = times;
818    }
819
820    pub fn hack_add_area(&mut self, area_type: AreaType, polygon: Polygon, osm_tags: Tags) {
821        self.areas.push(Area {
822            id: AreaID(self.areas.len()),
823            area_type,
824            polygon,
825            osm_tags,
826            osm_id: None,
827        });
828    }
829
830    /// Normally after applying edits, you must call `recalculate_pathfinding_after_edits`.
831    /// Alternatively, you can keep the old pathfinder exactly as it is. Use with caution -- the
832    /// pathfinder and the map may be out-of-sync in arbitrary ways.
833    pub fn keep_pathfinder_despite_edits(&mut self) {
834        self.pathfinder_dirty = false;
835    }
836
837    pub fn get_languages(&self) -> BTreeSet<String> {
838        let mut languages = BTreeSet::new();
839        for r in self.all_roads() {
840            for key in r.osm_tags.inner().keys() {
841                if let Some(x) = key.strip_prefix("name:") {
842                    languages.insert(x.to_string());
843                }
844            }
845        }
846        for b in self.all_buildings() {
847            for a in &b.amenities {
848                for lang in a.names.languages() {
849                    languages.insert(lang.to_string());
850                }
851            }
852        }
853        languages
854    }
855
856    pub fn get_config(&self) -> &MapConfig {
857        &self.config
858    }
859
860    /// Simple search along undirected roads. Expresses the result as a sequence of roads and a
861    /// sequence of intersections.
862    pub fn simple_path_btwn(
863        &self,
864        i1: IntersectionID,
865        i2: IntersectionID,
866    ) -> Option<(Vec<RoadID>, Vec<IntersectionID>)> {
867        let mut graph: UnGraphMap<IntersectionID, RoadID> = UnGraphMap::new();
868        for r in self.all_roads() {
869            if !r.is_light_rail() {
870                graph.add_edge(r.src_i, r.dst_i, r.id);
871            }
872        }
873        let (_, path) = petgraph::algo::astar(
874            &graph,
875            i1,
876            |i| i == i2,
877            |(_, _, r)| self.get_r(*r).length(),
878            |_| Distance::ZERO,
879        )?;
880        let roads: Vec<RoadID> = path
881            .windows(2)
882            .map(|pair| *graph.edge_weight(pair[0], pair[1]).unwrap())
883            .collect();
884        Some((roads, path))
885    }
886
887    /// Simple search along directed roads, weighted by distance. Expresses the result as a
888    /// sequence of roads and a sequence of intersections.
889    ///
890    /// Unlike the main pathfinding methods, this starts and ends at intersections. The first and
891    /// last step can be on any road connected to the intersection.
892    // TODO Remove simple_path_btwn in favor of this one?
893    pub fn simple_path_btwn_v2(
894        &self,
895        i1: IntersectionID,
896        i2: IntersectionID,
897        constraints: PathConstraints,
898    ) -> Option<(Vec<RoadID>, Vec<IntersectionID>)> {
899        let mut graph: DiGraphMap<IntersectionID, RoadID> = DiGraphMap::new();
900        for r in self.all_roads() {
901            let mut fwd = false;
902            let mut back = false;
903            for lane in &r.lanes {
904                if constraints.can_use(lane, self) {
905                    if lane.dir == Direction::Fwd {
906                        fwd = true;
907                    } else {
908                        back = true;
909                    }
910                }
911            }
912            if fwd {
913                graph.add_edge(r.src_i, r.dst_i, r.id);
914            }
915            if back {
916                graph.add_edge(r.dst_i, r.src_i, r.id);
917            }
918        }
919        let (_, path) = petgraph::algo::astar(
920            &graph,
921            i1,
922            |i| i == i2,
923            |(_, _, r)| self.get_r(*r).length(),
924            |_| Distance::ZERO,
925        )?;
926        let roads: Vec<RoadID> = path
927            .windows(2)
928            .map(|pair| *graph.edge_weight(pair[0], pair[1]).unwrap())
929            .collect();
930        Some((roads, path))
931    }
932
933    /// Returns the routing params baked into the map.
934    // Depending how this works out, we might require everybody to explicitly plumb routing params,
935    // in which case it should be easy to look for all places calling this.
936    pub fn routing_params(&self) -> &RoutingParams {
937        &self.routing_params
938    }
939
940    /// Adjusts the routing params baked into the map by accounting for any modal filters created
941    /// since.
942    /// TODO It's weird that these don't already take effect!
943    pub fn routing_params_respecting_modal_filters(&self) -> RoutingParams {
944        let mut params = self.routing_params.clone();
945        for r in &self.roads {
946            if r.modal_filter.is_some() {
947                params.avoid_roads.insert(r.id);
948            }
949        }
950        for i in &self.intersections {
951            if let Some(ref filter) = i.modal_filter {
952                params
953                    .avoid_movements_between
954                    .extend(filter.avoid_movements_between_roads());
955            }
956        }
957        params
958    }
959
960    pub fn road_to_buildings(&self, r: RoadID) -> &BTreeSet<BuildingID> {
961        self.road_to_buildings.get(r)
962    }
963
964    pub(crate) fn recalculate_road_to_buildings(&mut self) {
965        let mut mapping = MultiMap::new();
966        for b in self.all_buildings() {
967            mapping.insert(b.sidewalk_pos.lane().road, b.id);
968        }
969        self.road_to_buildings = mapping;
970    }
971
972    pub(crate) fn recalculate_all_movements(&mut self, timer: &mut Timer) {
973        let movements = timer.parallelize(
974            "generate movements",
975            self.intersections.iter().map(|i| i.id).collect(),
976            |i| Movement::for_i(i, self),
977        );
978        for (i, movements) in self.intersections.iter_mut().zip(movements.into_iter()) {
979            i.movements = movements;
980        }
981    }
982
983    /// Finds the road directly connecting two intersections.
984    pub fn find_road_between(&self, i1: IntersectionID, i2: IntersectionID) -> Option<RoadID> {
985        for r in &self.get_i(i1).roads {
986            let road = self.get_r(*r);
987            if road.src_i == i2 || road.dst_i == i2 {
988                return Some(road.id);
989            }
990        }
991        None
992    }
993
994    /// Returns the highest elevation in the map
995    pub fn max_elevation(&self) -> Distance {
996        // TODO Cache?
997        self.all_intersections()
998            .iter()
999            .max_by_key(|i| i.elevation)
1000            .unwrap()
1001            .elevation
1002    }
1003
1004    /// Does a turn at a stop sign go from a smaller to a larger road?
1005    /// (Note this doesn't look at unprotected movements in traffic signals, since we don't yet
1006    /// have good heuristics for when those exist)
1007    pub fn is_unprotected_turn(&self, from: RoadID, to: RoadID, turn_type: TurnType) -> bool {
1008        let unprotected_turn_type = if self.get_config().driving_side == DrivingSide::Right {
1009            TurnType::Left
1010        } else {
1011            TurnType::Right
1012        };
1013        let from = self.get_r(from);
1014        let to = self.get_r(to);
1015        turn_type == unprotected_turn_type
1016            && from.get_detailed_rank() < to.get_detailed_rank()
1017            && match from.common_endpoint(to) {
1018                CommonEndpoint::One(i) => self.get_i(i).is_stop_sign(),
1019                _ => false,
1020            }
1021    }
1022
1023    /// Modifies the map in-place, removing parts not essential for the bike network tool.
1024    pub fn minify(&mut self, timer: &mut Timer) {
1025        // We only need the CHs for driving and biking, to support mode shift.
1026        self.pathfinder = Pathfinder::new_limited(
1027            self,
1028            self.routing_params().clone(),
1029            crate::pathfind::CreateEngine::CH,
1030            vec![PathConstraints::Car, PathConstraints::Bike],
1031            timer,
1032        );
1033
1034        // Remove all routes, since we remove that pathfinder
1035        self.transit_stops.clear();
1036        self.transit_routes.clear();
1037        for r in &mut self.roads {
1038            r.transit_stops.clear();
1039        }
1040    }
1041
1042    /// Modifies the map in-place, removing buildings.
1043    pub fn minify_buildings(&mut self, timer: &mut Timer) {
1044        self.buildings.clear();
1045
1046        // We only need the CHs for driving.
1047        self.pathfinder = Pathfinder::new_limited(
1048            self,
1049            self.routing_params().clone(),
1050            crate::pathfind::CreateEngine::CH,
1051            vec![PathConstraints::Car],
1052            timer,
1053        );
1054
1055        // Remove all routes, since we remove that pathfinder
1056        self.transit_stops.clear();
1057        self.transit_routes.clear();
1058        for r in &mut self.roads {
1059            r.transit_stops.clear();
1060        }
1061    }
1062
1063    /// Export all road and intersection geometry to GeoJSON, transforming to WGS84
1064    pub fn export_geometry(&self) -> geojson::GeoJson {
1065        let mut pairs = Vec::new();
1066        let gps_bounds = Some(self.get_gps_bounds());
1067
1068        for i in self.all_intersections() {
1069            let mut props = serde_json::Map::new();
1070            props.insert("type".to_string(), "intersection".into());
1071            props.insert("id".to_string(), i.orig_id.to_string().into());
1072            pairs.push((i.polygon.get_outer_ring().to_geojson(gps_bounds), props));
1073        }
1074        for r in self.all_roads() {
1075            let mut props = serde_json::Map::new();
1076            props.insert("type".to_string(), "road".into());
1077            props.insert("id".to_string(), r.orig_id.osm_way_id.to_string().into());
1078            pairs.push((
1079                r.center_pts
1080                    .to_thick_ring(r.get_width())
1081                    .to_geojson(gps_bounds),
1082                props,
1083            ));
1084        }
1085
1086        geom::geometries_with_properties_to_geojson(pairs)
1087    }
1088
1089    /// What're the names of bus routes along a road? Note this is best effort, not robust to edits
1090    /// or transformations.
1091    pub fn get_bus_routes_on_road(&self, r: RoadID) -> &BTreeSet<String> {
1092        let way = self.get_r(r).orig_id.osm_way_id;
1093        self.bus_routes_on_roads.get(way)
1094    }
1095
1096    /// Find all amenity types that at least 1 building contains
1097    pub fn get_available_amenity_types(&self) -> BTreeSet<AmenityType> {
1098        let mut result = BTreeSet::new();
1099        for b in self.all_buildings() {
1100            for amenity in &b.amenities {
1101                if let Some(t) = AmenityType::categorize(&amenity.amenity_type) {
1102                    result.insert(t);
1103                }
1104            }
1105        }
1106        result
1107    }
1108
1109    // TODO This returns a mixture of different things related to the turn. It might be better
1110    // to create and return a `Turn`.
1111    pub fn get_ban_turn_info(
1112        &self,
1113        r1: &Road,
1114        r2: &Road,
1115        icon_counter: &HashMap<IntersectionID, i32>,
1116    ) -> (TurnType, Pt2D, Angle, IntersectionID) {
1117        // Determine where to place the symbol
1118        let i = match r1.common_endpoint(r2) {
1119            CommonEndpoint::One(i) => i,
1120            // This is probably rare, just pick one side arbitrarily
1121            CommonEndpoint::Both => r1.src_i,
1122            CommonEndpoint::None => {
1123                // This may be that `r1` and `r2` are joined by a complicated_turn_restrictions,
1124                // but don't have a CommonEndpoint.
1125                // In this case the end of r1 appears to be the most appropriate location to pick here
1126                r1.dst_i
1127            }
1128        };
1129
1130        // Determine where to place and orientate the icon
1131        let sign_count = *icon_counter.get(&i).unwrap_or(&1);
1132        let mut ideal_dist_from_intersection = sign_count as f64 * 1.1 * r1.get_width();
1133        if 2.0 * ideal_dist_from_intersection > r1.center_pts.length() {
1134            // We've run out of space on the road to fit all of the icons on. We will just pile them up where we can
1135            // Next try near the end of the stack, but just still in the appropriate half of the road
1136            ideal_dist_from_intersection = 0.5 * (r1.center_pts.length() - r1.get_width());
1137            if ideal_dist_from_intersection < Distance::ZERO {
1138                // The road is wider than it is long, so just squeeze them in:
1139                ideal_dist_from_intersection = 0.3 * r1.center_pts.length();
1140            }
1141        }
1142
1143        // Adjust according to which end of the road we've measuring from
1144        let dist_from_intersection = if r1.src_i == i {
1145            ideal_dist_from_intersection
1146        } else {
1147            r1.center_pts.length() - ideal_dist_from_intersection
1148        };
1149
1150        let (sign_pt, mut r1_angle) = r1.center_pts.must_dist_along(dist_from_intersection);
1151
1152        // Correct the angle, based on whether the vector direction is towards or away from the intersection
1153        // TODO what is the standard way of describing the vector direction (rather than the traffic direction) for roads?
1154        r1_angle = if r1.src_i == i {
1155            r1_angle.rotate_degs(180.0)
1156        } else {
1157            r1_angle
1158        };
1159
1160        let (_, mut r2_angle) = r2
1161            .center_pts
1162            .must_dist_along((if r2.src_i == i { 0.2 } else { 0.8 }) * r2.center_pts.length());
1163
1164        // Correct the angle, based on whether the vector direction is towards or away from the intersection
1165        r2_angle = if r2.dst_i == i {
1166            r2_angle.rotate_degs(180.0)
1167        } else {
1168            r2_angle
1169        };
1170
1171        let t_type = turn_type_from_road_geom(r1, r1_angle, r2, r2_angle, self.get_i(i), self);
1172        (t_type, sign_pt, r1_angle, i)
1173    }
1174}
1175
1176pub fn turn_type_from_road_geom(
1177    r1: &Road,
1178    r1_angle: Angle,
1179    r2: &Road,
1180    r2_angle: Angle,
1181    i: &Intersection,
1182    map: &Map,
1183) -> TurnType {
1184    let expected_turn_types = expected_turn_types_for_four_way(i, map);
1185
1186    let mut turn_type = turn_type_from_angles(r1_angle, r2_angle);
1187    if turn_type == TurnType::UTurn {
1188        // Lots of false positives when classifying these just based on angles. So also
1189        // require the road names to match.
1190
1191        if r1.get_name(None) != r2.get_name(None) {
1192            // Distinguish really sharp lefts/rights based on clockwiseness
1193            if r1_angle.simple_shortest_rotation_towards(r2_angle) < 0.0 {
1194                turn_type = TurnType::Right;
1195            } else {
1196                turn_type = TurnType::Left;
1197            }
1198        }
1199    } else if let Some(expected_type) = expected_turn_types
1200        .as_ref()
1201        .and_then(|e| e.get(&(r1.id, r2.id)))
1202    {
1203        // At some 4-way intersections, roads meet at strange angles, throwing off
1204        // turn_type_from_angles. Correct it based on relative ordering.
1205        if turn_type != *expected_type {
1206            warn!(
1207                "Turn from {} to {} looks like {:?} by angle, but is {:?} by ordering",
1208                r1.orig_id, r2.orig_id, turn_type, expected_type
1209            );
1210            turn_type = *expected_type;
1211        }
1212    }
1213    turn_type
1214}
1215
1216pub fn turn_type_from_angles(from: Angle, to: Angle) -> TurnType {
1217    let diff = from.simple_shortest_rotation_towards(to);
1218    // This is a pretty arbitrary parameter, but a difference of 30 degrees seems reasonable for
1219    // some observed cases.
1220    if diff.abs() < 30.0 {
1221        TurnType::Straight
1222    } else if diff.abs() > 135.0 {
1223        TurnType::UTurn
1224    } else if diff < 0.0 {
1225        // Clockwise rotation
1226        TurnType::Right
1227    } else {
1228        // Counter-clockwise rotation
1229        TurnType::Left
1230    }
1231}
1232
1233fn expected_turn_types_for_four_way(
1234    i: &Intersection,
1235    map: &Map,
1236) -> Option<HashMap<(RoadID, RoadID), TurnType>> {
1237    let roads = i.get_sorted_incoming_roads(map);
1238    if roads.len() != 4 {
1239        return None;
1240    }
1241
1242    // Just based on relative ordering around the intersection, turns (from road, to road, should
1243    // have this type)
1244    let mut expected_turn_types: HashMap<(RoadID, RoadID), TurnType> = HashMap::new();
1245    for (offset, turn_type) in [
1246        (1, TurnType::Left),
1247        (2, TurnType::Straight),
1248        (3, TurnType::Right),
1249    ] {
1250        for from_idx in 0..roads.len() {
1251            let to = *abstutil::wraparound_get(&roads, (from_idx as isize) + offset);
1252            expected_turn_types.insert((roads[from_idx], to), turn_type);
1253        }
1254    }
1255    Some(expected_turn_types)
1256}
map_model/map.rs

map_model/
map.rs
