map_model/make/
parking_lots.rs

1use std::collections::{HashMap, HashSet};
2
3use anyhow::Result;
4
5use abstutil::Timer;
6use geom::{Angle, Distance, FindClosest, HashablePt2D, Line, PolyLine, Polygon, Pt2D, Ring};
7use raw_map::RawParkingLot;
8
9use crate::make::{match_points_to_lanes, trim_path};
10use crate::{
11    osm, Map, ParkingLot, ParkingLotID, PathConstraints, Position, NORMAL_LANE_THICKNESS,
12    PARKING_LOT_SPOT_LENGTH,
13};
14
15/// Take in parking lots from OSM and all parking aisle roads. Match parking lots to the nearest
16/// sidewalk + driving lane, then automatically generate individual parking spots perpendicular to
17/// the aisles.
18pub fn make_all_parking_lots(
19    input: &[RawParkingLot],
20    aisles: &[(osm::WayID, Vec<Pt2D>)],
21    map: &Map,
22    timer: &mut Timer,
23) -> Vec<ParkingLot> {
24    timer.start("convert parking lots");
25    let mut center_per_lot: Vec<HashablePt2D> = Vec::new();
26    let mut query: HashSet<HashablePt2D> = HashSet::new();
27    for lot in input {
28        let center = lot.polygon.center().to_hashable();
29        center_per_lot.push(center);
30        query.insert(center);
31    }
32
33    let sidewalk_buffer = Distance::meters(7.5);
34    let sidewalk_pts = match_points_to_lanes(
35        map,
36        query,
37        |l| l.is_walkable(),
38        sidewalk_buffer,
39        Distance::meters(1000.0),
40        timer,
41    );
42
43    let mut results = Vec::new();
44    timer.start_iter("create parking lot driveways", center_per_lot.len());
45    for (lot_center, orig) in center_per_lot.into_iter().zip(input.iter()) {
46        timer.next();
47        match snap_driveway(lot_center, &orig.polygon, &sidewalk_pts, map) {
48            Ok((driveway_line, driving_pos, sidewalk_line, sidewalk_pos)) => {
49                let id = ParkingLotID(results.len());
50                results.push(ParkingLot {
51                    id,
52                    polygon: orig.polygon.clone(),
53                    aisles: Vec::new(),
54                    osm_id: orig.osm_id,
55                    spots: Vec::new(),
56                    extra_spots: 0,
57
58                    driveway_line,
59                    driving_pos,
60                    sidewalk_line,
61                    sidewalk_pos,
62                });
63            }
64            Err(err) => {
65                warn!("Skipping parking lot {}: {}", orig.osm_id, err);
66            }
67        }
68    }
69    info!(
70        "Discarded {} parking lots that weren't close enough to a sidewalk",
71        input.len() - results.len()
72    );
73
74    let mut closest: FindClosest<ParkingLotID> = FindClosest::new();
75    for lot in &results {
76        closest.add_polygon(lot.id, &lot.polygon);
77    }
78    timer.start_iter("match parking aisles", aisles.len());
79    for (aisle_id, pts) in aisles {
80        timer.next();
81        // Use the center of all the aisle points to match it to lots
82        let candidates: Vec<ParkingLotID> = closest
83            .all_close_pts(Pt2D::center(pts), Distance::meters(500.0))
84            .into_iter()
85            .map(|(id, _, _)| id)
86            .collect();
87
88        match Ring::split_points(pts) {
89            Ok((polylines, rings)) => {
90                for pl in polylines {
91                    for id in &candidates {
92                        let lot = &mut results[id.0];
93                        if let Some(segment) = lot.polygon.clip_polyline(&pl) {
94                            lot.aisles.push(segment);
95                            // A single aisle sometimes covers two adjacent parking lots -- like
96                            // https://www.openstreetmap.org/way/688540935. So allow for all
97                            // possible matches.
98                        }
99                    }
100                }
101                for ring in rings {
102                    for id in &candidates {
103                        let lot = &mut results[id.0];
104                        if let Some(segment) = lot.polygon.clip_ring(&ring) {
105                            lot.aisles.push(segment);
106                        }
107                    }
108                }
109            }
110            Err(err) => {
111                warn!("Parking aisle {} has weird geometry: {}", aisle_id, err);
112            }
113        }
114    }
115
116    let results = timer.parallelize("generate parking lot spots", results, |mut lot| {
117        lot.spots = infer_spots(&lot.polygon, &lot.aisles);
118
119        // Guess how many extra spots are available, that maybe aren't renderable.
120        if lot.spots.is_empty() {
121            // No parking aisles. Just guess based on the area. One spot per 30m^2 is a quick
122            // guess from looking at examples with aisles.
123            lot.extra_spots = (lot.polygon.area() / 30.0) as usize;
124        }
125
126        lot
127    });
128    timer.stop("convert parking lots");
129    results
130}
131
132/// Returns (driveway_line, driving_pos, sidewalk_line, sidewalk_pos)
133pub fn snap_driveway(
134    center: HashablePt2D,
135    polygon: &Polygon,
136    sidewalk_pts: &HashMap<HashablePt2D, Position>,
137    map: &Map,
138) -> Result<(PolyLine, Position, Line, Position)> {
139    let driveway_buffer = Distance::meters(7.0);
140
141    let sidewalk_pos = sidewalk_pts
142        .get(&center)
143        .ok_or_else(|| anyhow!("parking lot center didn't snap to a sidewalk"))?;
144    let sidewalk_line = match Line::new(center.to_pt2d(), sidewalk_pos.pt(map)) {
145        Ok(l) => trim_path(polygon, l),
146        Err(_) => {
147            bail!("front path has 0 length");
148        }
149    };
150
151    // Can this lot have a driveway? If it's not next to a driving lane, then no.
152    let mut driveway: Option<(PolyLine, Position)> = None;
153    let sidewalk_lane = sidewalk_pos.lane();
154    if let Some(driving_pos) = map
155        .get_parent(sidewalk_lane)
156        .find_closest_lane(sidewalk_lane, |l| PathConstraints::Car.can_use(l, map))
157        .and_then(|l| {
158            sidewalk_pos
159                .equiv_pos(l, map)
160                .buffer_dist(driveway_buffer, map)
161        })
162    {
163        if let Ok(pl) = PolyLine::new(vec![
164            sidewalk_line.pt1(),
165            sidewalk_line.pt2(),
166            driving_pos.pt(map),
167        ]) {
168            driveway = Some((pl, driving_pos));
169        }
170    }
171    let (driveway_line, driving_pos) = driveway.ok_or_else(|| {
172        anyhow!(
173            "snapped to sidewalk {}, but no driving connection",
174            sidewalk_pos.lane()
175        )
176    })?;
177    Ok((driveway_line, driving_pos, sidewalk_line, *sidewalk_pos))
178}
179
180fn infer_spots(lot_polygon: &Polygon, aisles: &[Vec<Pt2D>]) -> Vec<(Pt2D, Angle)> {
181    let mut spots = Vec::new();
182    let mut finalized_lines = Vec::new();
183
184    for aisle in aisles {
185        let aisle_thickness = NORMAL_LANE_THICKNESS / 2.0;
186        let pl = PolyLine::unchecked_new(aisle.clone());
187
188        for rotate in [90.0, -90.0] {
189            // Blindly generate all of the lines
190            let lines = {
191                let mut lines = Vec::new();
192                let mut start = Distance::ZERO;
193                while start + NORMAL_LANE_THICKNESS < pl.length() {
194                    let (pt, angle) = pl.must_dist_along(start);
195                    start += NORMAL_LANE_THICKNESS;
196                    let theta = angle.rotate_degs(rotate);
197                    lines.push(Line::must_new(
198                        pt.project_away(aisle_thickness / 2.0, theta),
199                        pt.project_away(aisle_thickness / 2.0 + PARKING_LOT_SPOT_LENGTH, theta),
200                    ));
201                }
202                lines
203            };
204
205            for pair in lines.windows(2) {
206                let l1 = &pair[0];
207                let l2 = &pair[1];
208                if let Ok(back) = Line::new(l1.pt2(), l2.pt2()) {
209                    if l1.intersection(l2).is_none()
210                        && l1.angle().approx_eq(l2.angle(), 5.0)
211                        && line_valid(lot_polygon, aisles, l1, &finalized_lines)
212                        && line_valid(lot_polygon, aisles, l2, &finalized_lines)
213                        && line_valid(lot_polygon, aisles, &back, &finalized_lines)
214                    {
215                        let avg_angle = Angle::average(vec![l1.angle(), l2.angle()]);
216                        spots.push((back.middle().unwrap(), avg_angle.opposite()));
217                        finalized_lines.push(l1.clone());
218                        finalized_lines.push(l2.clone());
219                        finalized_lines.push(back);
220                    }
221                }
222            }
223        }
224    }
225    spots
226}
227
228fn line_valid(
229    lot_polygon: &Polygon,
230    aisles: &[Vec<Pt2D>],
231    line: &Line,
232    finalized_lines: &[Line],
233) -> bool {
234    // Don't leak out of the parking lot
235    // TODO Entire line
236    if !lot_polygon.contains_pt(line.pt1()) || !lot_polygon.contains_pt(line.pt2()) {
237        return false;
238    }
239
240    // Don't let this line hit another line
241    if finalized_lines.iter().any(|other| line.crosses(other)) {
242        return false;
243    }
244
245    // Don't hit an aisle
246    if aisles.iter().any(|pts| {
247        PolyLine::unchecked_new(pts.clone())
248            .intersection(&line.to_polyline())
249            .is_some()
250    }) {
251        return false;
252    }
253
254    true
255}