1use std::collections::{BTreeSet, HashMap, HashSet};
2
3use anyhow::Result;
4use maplit::hashset;
5
6use abstutil::{prettyprint_usize, Counter, MultiMap, Timer};
7use geom::{Distance, PolyLine, Polygon, Time};
8use map_gui::tools::checkbox_per_mode;
9use map_model::{osm, BuildingID, BuildingType, IntersectionID, LaneID, Map, RoadID, TurnType};
10use sim::TripInfo;
11use synthpop::{TripEndpoint, TripMode};
12use widgetry::tools::{ColorLegend, PopupMsg};
13use widgetry::{
14 Color, Drawable, EventCtx, GeomBatch, GfxCtx, HorizontalAlignment, Key, Line, Outcome, Panel,
15 RewriteColor, Slider, State, Text, TextExt, Toggle, VerticalAlignment, Widget,
16};
17
18use crate::app::{App, Transition};
19use crate::common::CommonState;
20use crate::sandbox::dashboards::DashTab;
21
22pub struct CommuterPatterns {
23 bldg_to_block: HashMap<BuildingID, BlockID>,
24 border_to_block: HashMap<IntersectionID, BlockID>,
25 blocks: Vec<Block>,
26 current_block: (BlockSelection, Drawable),
27 filter: Filter,
28
29 trips_from_block: Vec<Vec<TripInfo>>,
31 trips_to_block: Vec<Vec<TripInfo>>,
32
33 panel: Panel,
34 draw_all_blocks: Drawable,
35}
36
37#[derive(PartialEq, Clone, Copy)]
38enum BlockSelection {
39 NothingSelected,
40 Unlocked(BlockID),
41 Locked {
42 base: BlockID,
43 compare_to: Option<BlockID>,
44 },
45}
46
47struct PanelState<'a> {
48 building_counts: Vec<(&'a str, u32)>,
49 max_count: usize,
50 total_trips: usize,
51}
52
53struct Block {
55 id: BlockID,
56 bldgs: HashSet<BuildingID>,
59 borders: HashSet<IntersectionID>,
60 shape: Polygon,
61}
62
63#[derive(PartialEq)]
64struct Filter {
65 from_block: bool,
67 include_borders: bool,
68 depart_from: Time,
69 depart_until: Time,
70 modes: BTreeSet<TripMode>,
71}
72
73type BlockID = usize;
74
75impl CommuterPatterns {
76 pub fn new_state(ctx: &mut EventCtx, app: &mut App) -> Box<dyn State<App>> {
77 let maybe_groups = ctx.loading_screen("group buildings into blocks", |_, timer| {
78 group_bldgs(app, timer)
79 });
80 let (bldg_to_block, border_to_block, blocks) = match maybe_groups {
81 Ok(result) => result,
82 Err(_) => {
83 return PopupMsg::new_state(
88 ctx,
89 "Error",
90 vec!["Problem rendering the grouped buildings; this tool won't work"],
91 );
92 }
93 };
94
95 let mut trips_from_block: Vec<Vec<TripInfo>> = std::iter::repeat_with(Vec::new)
96 .take(blocks.len())
97 .collect();
98 let mut trips_to_block: Vec<Vec<TripInfo>> = trips_from_block.clone();
99 for (_, trip) in app.primary.sim.all_trip_info() {
100 let block1 = match trip.start {
101 TripEndpoint::Building(b) => bldg_to_block[&b],
102 TripEndpoint::Border(i) => {
103 if let Some(block) = border_to_block.get(&i) {
104 *block
105 } else {
106 error!("No block for {i}?");
107 continue;
108 }
109 }
110 TripEndpoint::SuddenlyAppear(_) => continue,
111 };
112 let block2 = match trip.end {
113 TripEndpoint::Building(b) => bldg_to_block[&b],
114 TripEndpoint::Border(i) => {
115 if let Some(block) = border_to_block.get(&i) {
116 *block
117 } else {
118 error!("No block for {i}?");
119 continue;
120 }
121 }
122 TripEndpoint::SuddenlyAppear(_) => continue,
123 };
124 if block1 != block2 {
126 trips_from_block[block1].push(trip.clone());
127 trips_to_block[block2].push(trip);
128 }
129 }
130
131 let mut all_blocks = GeomBatch::new();
132 for block in &blocks {
133 all_blocks.push(Color::YELLOW.alpha(0.5), block.shape.clone());
134 }
135
136 let depart_until = app.primary.sim.get_end_of_day();
137
138 assert!(app.primary.suspended_sim.is_none());
139 app.primary.suspended_sim = Some(app.primary.clear_sim());
140
141 Box::new(CommuterPatterns {
142 bldg_to_block,
143 border_to_block,
144 blocks,
145 current_block: (BlockSelection::NothingSelected, Drawable::empty(ctx)),
146 trips_from_block,
147 trips_to_block,
148 filter: Filter {
149 from_block: true,
150 include_borders: true,
151 depart_from: Time::START_OF_DAY,
152 depart_until,
153 modes: TripMode::all().into_iter().collect(),
154 },
155
156 draw_all_blocks: ctx.upload(all_blocks),
157 panel: make_panel(ctx, app),
158 })
159 }
160
161 fn count_per_block(&self, base: &Block) -> Vec<(&Block, usize)> {
163 let candidates = if self.filter.from_block {
164 &self.trips_from_block[base.id]
165 } else {
166 &self.trips_to_block[base.id]
167 };
168 let mut count: Counter<BlockID> = Counter::new();
169 for trip in candidates {
170 if trip.departure < self.filter.depart_from || trip.departure > self.filter.depart_until
171 {
172 continue;
173 }
174 if !self.filter.modes.contains(&trip.mode) {
175 continue;
176 }
177 if self.filter.from_block {
178 match trip.end {
179 TripEndpoint::Building(b) => {
180 count.inc(self.bldg_to_block[&b]);
181 }
182 TripEndpoint::Border(i) => {
183 if self.filter.include_borders {
184 count.inc(self.border_to_block[&i]);
185 }
186 }
187 TripEndpoint::SuddenlyAppear(_) => {}
188 }
189 } else {
190 match trip.start {
191 TripEndpoint::Building(b) => {
192 count.inc(self.bldg_to_block[&b]);
193 }
194 TripEndpoint::Border(i) => {
195 if self.filter.include_borders {
196 count.inc(self.border_to_block[&i]);
197 }
198 }
199 TripEndpoint::SuddenlyAppear(_) => {}
200 }
201 }
202 }
203
204 count
205 .consume()
206 .into_iter()
207 .map(|(id, cnt)| (&self.blocks[id], cnt))
208 .collect()
209 }
210
211 fn build_block_drawable<'a>(
212 &self,
213 block_selection: BlockSelection,
214 ctx: &EventCtx,
215 app: &App,
216 ) -> (Drawable, Option<PanelState<'a>>) {
217 let mut batch = GeomBatch::new();
218
219 let base_block_id = match block_selection {
220 BlockSelection::Unlocked(id) => Some(id),
221 BlockSelection::Locked { base, .. } => Some(base),
222 BlockSelection::NothingSelected => None,
223 };
224
225 match base_block_id {
226 None => (ctx.upload(batch), None),
227 Some(base_block_id) => {
228 let base_block = &self.blocks[base_block_id];
229
230 let mut building_counts: Vec<(&'a str, u32)> = vec![
232 ("Residential", 0),
233 ("Residential/Commercial", 0),
234 ("Commercial", 0),
235 ("Empty", 0),
236 ];
237 for b in &base_block.bldgs {
238 let b = app.primary.map.get_b(*b);
239 batch.push(Color::PURPLE, b.polygon.clone());
240 match b.bldg_type {
241 BuildingType::Residential { .. } => building_counts[0].1 += 1,
242 BuildingType::ResidentialCommercial(_, _) => building_counts[1].1 += 1,
243 BuildingType::Commercial(_) => building_counts[2].1 += 1,
244 BuildingType::Empty => building_counts[3].1 += 1,
245 }
246 }
247 for i in &base_block.borders {
248 batch.push(Color::PURPLE, app.primary.map.get_i(*i).polygon.clone());
249 }
250
251 batch.push(Color::BLACK.alpha(0.5), base_block.shape.clone());
252
253 if let BlockSelection::Locked { .. } = block_selection {
255 batch.push(
256 Color::BLACK,
257 base_block.shape.to_outline(Distance::meters(10.0)),
258 );
259 }
260
261 {
262 let (icon_name, icon_scale) = if self.filter.from_block {
264 ("outward.svg", 1.2)
265 } else {
266 ("inward.svg", 1.0)
267 };
268
269 let center = base_block.shape.polylabel();
270 let icon = GeomBatch::load_svg(
271 ctx.prerender,
272 format!("system/assets/tools/{}", icon_name),
273 )
274 .scale(icon_scale)
275 .centered_on(center)
276 .color(RewriteColor::ChangeAll(Color::WHITE));
277
278 batch.append(icon);
279 }
280
281 let others = self.count_per_block(base_block);
282
283 let mut total_trips = 0;
284 let max_count = others.iter().map(|(_, cnt)| *cnt).max().unwrap_or(0);
285 for (other, cnt) in &others {
286 total_trips += cnt;
287 let pct = (*cnt as f64) / (max_count as f64);
288 batch.push(
289 app.cs.good_to_bad_red.eval(pct).alpha(0.8),
290 other.shape.clone(),
291 );
292 }
293
294 if let BlockSelection::Locked {
297 base: _,
298 compare_to: Some(compare_to),
299 } = block_selection
300 {
301 let compare_to_block = &self.blocks[compare_to];
302
303 let border = compare_to_block.shape.to_outline(Distance::meters(10.0));
304 batch.push(Color::WHITE.alpha(0.8), border);
305
306 let count = others
307 .into_iter()
308 .find(|(b, _)| b.id == compare_to)
309 .map(|(_, count)| count)
310 .unwrap_or(0);
311 let label_text = abstutil::prettyprint_usize(count);
312 let label = Text::from(Line(label_text).fg(Color::BLACK))
313 .render_autocropped(ctx)
314 .scale(2.0)
315 .centered_on(compare_to_block.shape.polylabel());
316
317 let dims = label.get_dims();
318 let label_bg = Polygon::pill(dims.width + 70.0, dims.height + 20.0);
319 let bg = GeomBatch::from(vec![(Color::WHITE, label_bg)])
320 .centered_on(compare_to_block.shape.polylabel());
321 batch.append(bg);
322 batch.append(label);
323 };
324 let panel_data = PanelState {
325 building_counts,
326 max_count,
327 total_trips,
328 };
329 (ctx.upload(batch), Some(panel_data))
330 }
331 }
332 }
333
334 fn redraw_panel(&mut self, state: Option<&PanelState>, ctx: &mut EventCtx, app: &App) {
335 if let Some(state) = state {
336 let mut txt = Text::new();
337 txt.add_line(format!(
338 "Total: {} trips",
339 abstutil::prettyprint_usize(state.total_trips)
340 ));
341
342 for (name, cnt) in &state.building_counts {
343 if *cnt != 0 {
344 txt.add_line(format!("{}: {}", name, cnt));
345 }
346 }
347
348 self.panel.replace(ctx, "current", txt.into_widget(ctx));
349
350 let new_scale = ColorLegend::gradient(
351 ctx,
352 &app.cs.good_to_bad_red,
353 vec![
354 "0".to_string(),
355 format!("{} trips", prettyprint_usize(state.max_count)),
356 ],
357 );
358 self.panel.replace(ctx, "scale", new_scale);
359 } else {
360 self.panel
361 .replace(ctx, "current", "None selected".text_widget(ctx));
362 }
363 }
364}
365
366impl State<App> for CommuterPatterns {
367 fn event(&mut self, ctx: &mut EventCtx, app: &mut App) -> Transition {
368 ctx.canvas_movement();
369
370 match self.panel.event(ctx) {
371 Outcome::Clicked(x) => match x.as_ref() {
372 "close" => {
373 app.primary.sim = app.primary.suspended_sim.take().unwrap();
374 return Transition::Pop;
375 }
376 _ => unreachable!(),
377 },
378 Outcome::Changed(_) => {
379 if let Some(tab) = DashTab::CommuterPatterns.tab_changed(app, &self.panel) {
380 app.primary.sim = app.primary.suspended_sim.take().unwrap();
381 return Transition::Replace(tab.launch(ctx, app));
382 }
383 }
384 _ => {}
385 }
386
387 let block_selection = if let Some(Some(b)) = ctx
388 .canvas
389 .get_cursor_in_map_space()
390 .map(|pt| self.blocks.iter().find(|b| b.shape.contains_pt(pt)))
391 {
392 if app.per_obj.left_click(ctx, "clicked block") {
393 match self.current_block.0 {
394 BlockSelection::Locked { base: old_base, .. } => {
395 if old_base == b.id {
396 BlockSelection::Unlocked(b.id)
397 } else {
398 BlockSelection::Locked {
399 base: b.id,
400 compare_to: None,
401 }
402 }
403 }
404 _ => BlockSelection::Locked {
405 base: b.id,
406 compare_to: None,
407 },
408 }
409 } else {
410 match self.current_block.0 {
412 BlockSelection::Locked { base, .. } => {
413 if base == b.id {
414 BlockSelection::Locked {
415 base,
416 compare_to: None,
417 }
418 } else {
419 BlockSelection::Locked {
420 base,
421 compare_to: Some(b.id),
422 }
423 }
424 }
425 BlockSelection::Unlocked(_) => BlockSelection::Unlocked(b.id),
426 BlockSelection::NothingSelected => BlockSelection::Unlocked(b.id),
427 }
428 }
429 } else {
430 match self.current_block.0 {
432 BlockSelection::NothingSelected | BlockSelection::Unlocked(_) => {
433 BlockSelection::NothingSelected
434 }
435 BlockSelection::Locked { base, .. } => BlockSelection::Locked {
436 base,
437 compare_to: None,
438 },
439 }
440 };
441
442 let mut filter = Filter {
443 from_block: self.panel.is_checked("from / to this block"),
444 include_borders: self.panel.is_checked("include borders"),
445 depart_from: app
446 .primary
447 .sim
448 .get_end_of_day()
449 .percent_of(self.panel.slider("depart from").get_percent()),
450 depart_until: app
451 .primary
452 .sim
453 .get_end_of_day()
454 .percent_of(self.panel.slider("depart until").get_percent()),
455 modes: BTreeSet::new(),
456 };
457 for m in TripMode::all() {
458 if self.panel.is_checked(m.ongoing_verb()) {
459 filter.modes.insert(m);
460 }
461 }
462
463 if filter != self.filter || block_selection != self.current_block.0 {
464 self.filter = filter;
465 let (drawable, per_block_counts) = self.build_block_drawable(block_selection, ctx, app);
466 self.redraw_panel(per_block_counts.as_ref(), ctx, app);
467 self.current_block = (block_selection, drawable);
468 }
469 Transition::Keep
470 }
471
472 fn draw(&self, g: &mut GfxCtx, app: &App) {
473 g.redraw(&self.draw_all_blocks);
474 g.redraw(&self.current_block.1);
475
476 self.panel.draw(g);
477 CommonState::draw_osd(g, app);
478 }
479}
480
481fn group_bldgs(
486 app: &App,
487 timer: &mut Timer,
488) -> Result<(
489 HashMap<BuildingID, BlockID>,
490 HashMap<IntersectionID, BlockID>,
491 Vec<Block>,
492)> {
493 let mut bldg_to_block = HashMap::new();
494 let mut blocks = Vec::new();
495
496 let map = &app.primary.map;
497 for maybe_block in timer.parallelize(
498 "draw neighborhoods",
499 partition_sidewalk_loops(app)
500 .into_iter()
501 .enumerate()
502 .collect(),
503 |(block_id, group)| {
504 let mut hull_points = Vec::new();
505 let mut lanes = HashSet::new();
506 for b in &group.bldgs {
507 let bldg = map.get_b(*b);
508 if group.proper {
509 lanes.insert(bldg.sidewalk());
510 }
511 hull_points.append(&mut bldg.polygon.get_outer_ring().clone().into_points());
512 }
513 if group.proper {
514 for l in lanes {
516 let lane_line = map
517 .get_l(l)
518 .lane_center_pts
519 .interpolate_points(Distance::meters(20.0));
520 hull_points.append(&mut lane_line.points().clone());
521 }
522 }
523 Polygon::concave_hull(hull_points, 10).map(|shape| Block {
524 id: block_id,
525 bldgs: group.bldgs,
526 borders: HashSet::new(),
527 shape,
528 })
529 },
530 ) {
531 let block = maybe_block?;
532 for b in &block.bldgs {
533 bldg_to_block.insert(*b, block.id);
534 }
535 blocks.push(block);
536 }
537
538 let mut border_to_block = HashMap::new();
539 for i in app.primary.map.all_incoming_borders() {
540 let id = blocks.len();
541 border_to_block.insert(i.id, id);
542 blocks.push(Block {
543 id,
544 bldgs: HashSet::new(),
545 borders: hashset! { i.id },
546 shape: build_shape_for_border(i, BorderType::Incoming, &app.primary.map),
547 });
548 }
549 for i in app.primary.map.all_outgoing_borders() {
550 if let Some(incoming_border_id) = border_to_block.get(&i.id) {
551 let two_way_border = &mut blocks[*incoming_border_id];
552 two_way_border.shape = build_shape_for_border(i, BorderType::Both, &app.primary.map);
553 continue;
554 }
555 let id = blocks.len();
556 border_to_block.insert(i.id, id);
557
558 blocks.push(Block {
559 id,
560 bldgs: HashSet::new(),
561 borders: hashset! { i.id },
562 shape: build_shape_for_border(i, BorderType::Outgoing, &app.primary.map),
563 });
564 }
565
566 Ok((bldg_to_block, border_to_block, blocks))
567}
568
569enum BorderType {
570 Incoming,
571 Outgoing,
572 Both,
573}
574
575fn build_shape_for_border(
576 border: &map_model::Intersection,
577 border_type: BorderType,
578 map: &Map,
579) -> Polygon {
580 let start = border.polygon.center();
581
582 let road = map.get_r(*border.roads.iter().next().unwrap());
583 let center_line = road.get_dir_change_pl(map);
584 let angle = if road.src_i == border.id {
585 center_line.first_line().angle().opposite()
586 } else {
587 center_line.first_line().angle()
588 };
589
590 let length = Distance::meters(150.0);
591 let thickness = Distance::meters(30.0);
592 let end = start.project_away(length, angle);
593
594 match border_type {
595 BorderType::Incoming => {
596 PolyLine::must_new(vec![end, start]).make_arrow(thickness, geom::ArrowCap::Triangle)
597 }
598 BorderType::Outgoing => {
599 PolyLine::must_new(vec![start, end]).make_arrow(thickness, geom::ArrowCap::Triangle)
600 }
601 BorderType::Both => PolyLine::must_new(vec![start, end])
602 .make_double_arrow(thickness, geom::ArrowCap::Triangle),
603 }
604}
605
606struct Loop {
607 bldgs: HashSet<BuildingID>,
608 proper: bool,
610 roads: HashSet<RoadID>,
611}
612
613fn partition_sidewalk_loops(app: &App) -> Vec<Loop> {
614 let map = &app.primary.map;
615
616 let mut groups = Vec::new();
617 let mut todo_bldgs: BTreeSet<BuildingID> = map.all_buildings().iter().map(|b| b.id).collect();
618 let mut remainder = HashSet::new();
619
620 let mut sidewalk_to_bldgs = MultiMap::new();
621 for b in map.all_buildings() {
622 sidewalk_to_bldgs.insert(b.sidewalk(), b.id);
623 }
624
625 while !todo_bldgs.is_empty() {
626 let mut sidewalks = HashSet::new();
627 let mut bldgs = HashSet::new();
628 let mut current_l = map.get_b(*todo_bldgs.iter().next().unwrap()).sidewalk();
629 let mut current_i = map.get_l(current_l).src_i;
630
631 let ok = loop {
632 sidewalks.insert(current_l);
633 for b in sidewalk_to_bldgs.get(current_l) {
634 bldgs.insert(*b);
635 todo_bldgs.remove(b);
637 }
638
639 let turns = map
641 .get_next_turns_and_lanes(current_l)
642 .into_iter()
643 .map(|(t, _)| t)
644 .filter(|t| {
645 t.turn_type == TurnType::SharedSidewalkCorner && t.id.parent != current_i
646 })
647 .collect::<Vec<_>>();
648 if turns.is_empty() {
649 break false;
652 } else if turns.len() == 1 {
653 current_l = if turns[0].id.dst != current_l {
654 turns[0].id.dst
655 } else {
656 turns[0].id.src
657 };
658 current_i = turns[0].id.parent;
659 if sidewalks.contains(¤t_l) {
660 break true;
662 }
663 } else {
664 break false;
667 };
668 };
669
670 if ok {
671 groups.push(Loop {
672 bldgs,
673 proper: true,
674 roads: sidewalks.into_iter().map(|l| l.road).collect(),
675 });
676 } else {
677 remainder.extend(bldgs);
678 }
679 }
680
681 loop {
683 let mut any = false;
685 for mut idx1 in 0..groups.len() {
686 for mut idx2 in 0..groups.len() {
687 if idx1 >= groups.len() || idx2 >= groups.len() {
691 break;
692 }
693
694 if idx1 != idx2
695 && groups[idx1]
696 .roads
697 .intersection(&groups[idx2].roads)
698 .any(|r| map.get_r(*r).get_rank() == osm::RoadRank::Local)
699 {
700 if idx1 > idx2 {
702 std::mem::swap(&mut idx1, &mut idx2);
703 }
704 let merge = groups.remove(idx2);
705 groups[idx1].bldgs.extend(merge.bldgs);
706 groups[idx1].roads.extend(merge.roads);
707 any = true;
708 }
709 }
710 }
711 if !any {
712 break;
713 }
714 }
715
716 let mut per_sidewalk: MultiMap<LaneID, BuildingID> = MultiMap::new();
718 for b in remainder {
719 per_sidewalk.insert(map.get_b(b).sidewalk(), b);
720 }
721 for (_, bldgs) in per_sidewalk.consume() {
722 let r = map.get_b(*bldgs.iter().next().unwrap()).sidewalk().road;
723 groups.push(Loop {
724 bldgs: bldgs.into_iter().collect(),
725 proper: false,
726 roads: hashset! { r },
727 });
728 }
729
730 groups
731}
732
733fn make_panel(ctx: &mut EventCtx, app: &App) -> Panel {
734 Panel::new_builder(Widget::col(vec![
735 DashTab::CommuterPatterns.picker(ctx, app),
736 Toggle::choice(ctx, "from / to this block", "from", "to", Key::Space, true),
737 Toggle::switch(ctx, "include borders", None, true),
738 Widget::row(vec![
739 "Departing from:".text_widget(ctx).margin_right(20),
740 Slider::area(ctx, 0.15 * ctx.canvas.window_width, 0.0, "depart from"),
741 ]),
742 Widget::row(vec![
743 "Departing until:".text_widget(ctx).margin_right(20),
744 Slider::area(ctx, 0.15 * ctx.canvas.window_width, 1.0, "depart until"),
745 ]),
746 checkbox_per_mode(ctx, app, &TripMode::all().into_iter().collect()),
747 ColorLegend::gradient(ctx, &app.cs.good_to_bad_red, vec!["0", "0"]).named("scale"),
748 "None selected".text_widget(ctx).named("current"),
749 ]))
750 .aligned(HorizontalAlignment::Right, VerticalAlignment::Top)
751 .build(ctx)
752}