map_model/objects/
zone.rs

1//! Zones and AccessRestrictions are used to model things like:
2//! 1) gated communities, where only trips beginning or ending at a building in the neighborhood may
3//!    use any of the private roads
4//! 2) Stay Healthy Streets, where most car traffic is banned, except for trips beginning/ending in
5//!    the zone
6//! 3) Congestion capping, where only so many cars per hour can enter the zone
7
8use std::collections::BTreeSet;
9
10use enumset::EnumSet;
11use serde::{Deserialize, Serialize};
12
13use crate::{CommonEndpoint, IntersectionID, Map, PathConstraints, RoadID};
14
15#[derive(Serialize, Deserialize, Debug, PartialEq, Clone)]
16pub struct AccessRestrictions {
17    pub allow_through_traffic: EnumSet<PathConstraints>,
18}
19
20impl AccessRestrictions {
21    pub fn new() -> AccessRestrictions {
22        AccessRestrictions {
23            allow_through_traffic: EnumSet::all(),
24        }
25    }
26}
27
28/// A contiguous set of roads with access restrictions. This is derived from all the map's roads and
29/// kept cached for performance.
30#[derive(Serialize, Deserialize, Clone, Debug, PartialEq)]
31pub struct Zone {
32    pub members: BTreeSet<RoadID>,
33    pub borders: BTreeSet<IntersectionID>,
34    pub restrictions: AccessRestrictions,
35}
36
37impl Zone {
38    pub fn make_all(map: &Map) -> Vec<Zone> {
39        let mut queue = Vec::new();
40        for r in map.all_roads() {
41            if r.is_private() {
42                queue.push(r.id);
43            }
44        }
45
46        let mut zones = Vec::new();
47        let mut seen = BTreeSet::new();
48        while !queue.is_empty() {
49            let start = queue.pop().unwrap();
50            if seen.contains(&start) {
51                continue;
52            }
53            if let Some(zone) = floodfill(map, start) {
54                seen.extend(zone.members.clone());
55                zones.push(zone);
56            }
57        }
58
59        zones
60    }
61}
62
63fn floodfill(map: &Map, start: RoadID) -> Option<Zone> {
64    let match_constraints = map.get_r(start).access_restrictions.clone();
65    let mut queue = vec![start];
66    let mut members = BTreeSet::new();
67    let mut borders = BTreeSet::new();
68    while !queue.is_empty() {
69        let current = queue.pop().unwrap();
70        if members.contains(&current) {
71            continue;
72        }
73        members.insert(current);
74        for r in map.get_next_roads(current) {
75            let r = map.get_r(r);
76            if r.access_restrictions == match_constraints {
77                queue.push(r.id);
78            } else {
79                // TODO Handle other cases
80                if let CommonEndpoint::One(i) = map.get_r(current).common_endpoint(r) {
81                    borders.insert(i);
82                }
83            }
84        }
85    }
86    assert!(!members.is_empty());
87    if borders.is_empty() {
88        // This can happen around cases like https://www.openstreetmap.org/way/572240785 where the
89        // intersection geometry seems to break
90        return None;
91    }
92    Some(Zone {
93        members,
94        borders,
95        restrictions: match_constraints,
96    })
97}