1use std::collections::HashSet;
2
3use rand::{Rng, SeedableRng};
4use rand_xorshift::XorShiftRng;
5
6use abstutil::Timer;
7use geom::{Distance, Polygon, QuadTree};
8use map_model::{osm, Map};
9
10pub fn run(map: String, num_required: usize, rng_seed: u64, output: String) {
11 let mut timer = Timer::new("generate houses");
12 let mut rng = XorShiftRng::seed_from_u64(rng_seed);
13 let map = Map::load_synchronously(map, &mut timer);
14
15 let houses = generate_buildings_on_empty_residential_roads(&map, &mut rng, &mut timer);
16 if houses.len() <= num_required {
17 panic!(
18 "Only generated {} houses, but wanted at least {}",
19 houses.len(),
20 num_required
21 );
22 }
23
24 abstio::write_json(
25 output,
26 &geom::geometries_to_geojson(
27 houses
28 .into_iter()
29 .map(|poly| poly.to_geojson(Some(map.get_gps_bounds())))
30 .collect(),
31 ),
32 );
33}
34
35fn generate_buildings_on_empty_residential_roads(
36 map: &Map,
37 rng: &mut XorShiftRng,
38 timer: &mut Timer,
39) -> Vec<Polygon> {
40 timer.start("initially place buildings");
41 let mut lanes_with_buildings = HashSet::new();
42 for b in map.all_buildings() {
43 lanes_with_buildings.insert(b.sidewalk());
44 }
45
46 let mut empty_sidewalks = Vec::new();
48 for l in map.all_lanes() {
49 if l.is_sidewalk()
50 && !lanes_with_buildings.contains(&l.id)
51 && map
52 .get_parent(l.id)
53 .osm_tags
54 .is(osm::HIGHWAY, "residential")
55 {
56 empty_sidewalks.push(l.id);
57 }
58 }
59
60 let mut houses = Vec::new();
63 for l in empty_sidewalks {
64 let lane = map.get_l(l);
65 let mut dist_along = rand_dist(rng, 1.0, 5.0);
66 while dist_along < lane.length() {
67 let (sidewalk_pt, angle) = lane.lane_center_pts.must_dist_along(dist_along);
68 let width = rng.gen_range(6.0..14.0);
69 let height = rng.gen_range(6.0..14.0);
70
71 let setback = Distance::meters(10.0) + Distance::meters(height / 2.0);
74 let center = sidewalk_pt.project_away(setback, angle.rotate_degs(-90.0));
75
76 houses.push(
77 Polygon::rectangle(width, height)
78 .rotate(angle)
79 .translate(center.x() - width / 2.0, center.y() - height / 2.0),
80 );
81
82 dist_along += Distance::meters(width.max(height)) + rand_dist(rng, 2.0, 4.0);
83 }
84 }
85 timer.stop("initially place buildings");
86
87 let mut non_overlapping = Vec::new();
90 let mut quadtree = QuadTree::new();
91 timer.start_iter("prune buildings overlapping each other", houses.len());
92 'HOUSE: for poly in houses {
93 timer.next();
94 let mut search = poly.get_bounds();
95 search.add_buffer(Distance::meters(1.0));
96 for idx in quadtree.query_bbox(search) {
97 if poly.intersects(&non_overlapping[idx]) {
98 continue 'HOUSE;
99 }
100 }
101 quadtree.insert_with_box(non_overlapping.len(), poly.get_bounds());
102 non_overlapping.push(poly);
103 }
104
105 let mut quadtree = QuadTree::builder();
108 let mut static_polygons = Vec::new();
109 for r in map.all_roads() {
110 let poly = r.get_thick_polygon();
111 quadtree.add_with_box(static_polygons.len(), poly.get_bounds());
112 static_polygons.push(poly);
113 }
114 for i in map.all_intersections() {
115 quadtree.add_with_box(static_polygons.len(), i.polygon.get_bounds());
116 static_polygons.push(i.polygon.clone());
117 }
118 for b in map.all_buildings() {
119 quadtree.add_with_box(static_polygons.len(), b.polygon.get_bounds());
120 static_polygons.push(b.polygon.clone());
121 }
122 for pl in map.all_parking_lots() {
123 quadtree.add_with_box(static_polygons.len(), pl.polygon.get_bounds());
124 static_polygons.push(pl.polygon.clone());
125 }
126 for a in map.all_areas() {
127 quadtree.add_with_box(static_polygons.len(), a.polygon.get_bounds());
128 static_polygons.push(a.polygon.clone());
129 }
130 let quadtree = quadtree.build();
131
132 let mut survivors = Vec::new();
133 timer.start_iter(
134 "prune buildings overlapping the basemap",
135 non_overlapping.len(),
136 );
137 'NON_OVERLAP: for poly in non_overlapping {
138 timer.next();
139 for idx in quadtree.query_bbox(poly.get_bounds()) {
140 if poly.intersects(&static_polygons[idx]) {
141 continue 'NON_OVERLAP;
142 }
143 }
144 survivors.push(poly);
145 }
146 survivors
147}
148
149fn rand_dist(rng: &mut XorShiftRng, low: f64, high: f64) -> Distance {
150 assert!(high > low);
151 Distance::meters(rng.gen_range(low..high))
152}