use std::collections::{BTreeMap, BTreeSet};
use anyhow::Result;
use serde::{Deserialize, Serialize};
use abstio::MapName;
use abstutil::Timer;
use blockfinding::{Block, Perimeter};
use geom::Polygon;
use map_model::osm::RoadRank;
use map_model::{IntersectionID, Map, RoadID, RoadSideID};
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub struct NeighbourhoodID(pub usize);
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub struct BlockID(usize);
impl widgetry::mapspace::ObjectID for NeighbourhoodID {}
impl widgetry::mapspace::ObjectID for BlockID {}
#[derive(Clone, Serialize, Deserialize)]
pub struct Partitioning {
pub map: MapName,
neighbourhoods: BTreeMap<NeighbourhoodID, NeighbourhoodInfo>,
single_blocks: Vec<Block>,
neighbourhood_id_counter: usize,
block_to_neighbourhood: BTreeMap<BlockID, NeighbourhoodID>,
pub broken: bool,
#[serde(skip_serializing, skip_deserializing)]
pub custom_boundaries: BTreeMap<NeighbourhoodID, CustomBoundary>,
}
#[derive(Clone, Serialize, Deserialize)]
pub struct NeighbourhoodInfo {
pub block: Block,
pub override_drawing_boundary: Option<Polygon>,
}
impl NeighbourhoodInfo {
fn new(block: Block) -> Self {
Self {
block,
override_drawing_boundary: None,
}
}
}
#[derive(Clone)]
pub struct CustomBoundary {
pub name: String,
pub boundary_polygon: Polygon,
pub borders: BTreeSet<IntersectionID>,
pub interior_roads: BTreeSet<RoadID>,
}
impl Partitioning {
pub fn empty() -> Partitioning {
Partitioning {
map: MapName::new("zz", "temp", "orary"),
neighbourhoods: BTreeMap::new(),
single_blocks: Vec::new(),
neighbourhood_id_counter: 0,
block_to_neighbourhood: BTreeMap::new(),
broken: false,
custom_boundaries: BTreeMap::new(),
}
}
pub fn is_empty(&self) -> bool {
self.neighbourhoods.is_empty()
}
pub fn seed_using_heuristics(map: &Map, timer: &mut Timer) -> Partitioning {
timer.start("seed partitioning with heuristics");
timer.start("find single blocks");
let input_single_blocks = Perimeter::find_all_single_blocks(map);
timer.stop("find single blocks");
timer.start("merge holes");
let input = Perimeter::merge_holes(map, input_single_blocks);
timer.stop("merge holes");
let mut single_blocks = Vec::new();
let mut single_block_perims = Vec::new();
timer.start_iter("fix deadends and blockify", input.len());
for mut perim in input {
timer.next();
perim.collapse_deadends();
if let Ok(block) = perim.to_block(map) {
single_block_perims.push(block.perimeter.clone());
single_blocks.push(block);
}
}
timer.start("partition");
let partitions = Perimeter::partition_by_predicate(single_block_perims, |r| {
map.get_r(r).get_rank() == RoadRank::Local
});
let mut merged = Vec::new();
for perimeters in partitions {
let stepwise_debug = false;
merged.extend(Perimeter::merge_all(map, perimeters, stepwise_debug));
}
timer.stop("partition");
timer.start_iter("blockify merged", merged.len());
let mut blocks = Vec::new();
for perimeter in merged {
timer.next();
match perimeter.to_block(map) {
Ok(block) => {
blocks.push(block);
}
Err(err) => {
warn!("Failed to make a block from a merged perimeter: {}", err);
}
}
}
let mut neighbourhoods = BTreeMap::new();
for block in blocks {
neighbourhoods.insert(
NeighbourhoodID(neighbourhoods.len()),
NeighbourhoodInfo::new(block),
);
}
let neighbourhood_id_counter = neighbourhoods.len();
let mut p = Partitioning {
map: map.get_name().clone(),
neighbourhoods,
single_blocks,
neighbourhood_id_counter,
block_to_neighbourhood: BTreeMap::new(),
broken: false,
custom_boundaries: BTreeMap::new(),
};
for id in p.all_block_ids() {
if let Some(neighbourhood) = p.neighbourhood_containing(id) {
p.block_to_neighbourhood.insert(id, neighbourhood);
} else {
error!(
"Block doesn't belong to any neighbourhood. Continuing without boundary adjustment. {:?}",
p.get_block(id).perimeter
);
p.broken = true;
}
}
timer.stop("seed partitioning with heuristics");
p
}
pub fn transfer_blocks(
&mut self,
map: &Map,
add_all: Vec<BlockID>,
new_owner: NeighbourhoodID,
) -> Result<Option<NeighbourhoodID>> {
let mut new_owner_blocks = self.neighbourhood_to_blocks(new_owner);
new_owner_blocks.extend(add_all.clone());
let mut new_neighbourhood_blocks = self.make_merged_blocks(map, new_owner_blocks)?;
if new_neighbourhood_blocks.len() != 1 {
bail!("Couldn't add block -- you may need to add an intermediate block first to avoid a hole, or there's a bug you can't workaround yet. Try adding pink blocks first.");
}
let new_neighbourhood_block = new_neighbourhood_blocks.pop().unwrap();
let old_owners: BTreeSet<NeighbourhoodID> = add_all
.iter()
.map(|block| self.block_to_neighbourhood[block])
.collect();
let mut return_value = None;
for old_owner in old_owners {
let mut old_owner_blocks = self.neighbourhood_to_blocks(old_owner);
for x in &add_all {
old_owner_blocks.remove(x);
}
if old_owner_blocks.is_empty() {
self.neighbourhoods.remove(&old_owner).unwrap();
return_value = Some(new_owner);
continue;
}
let mut old_neighbourhood_blocks =
self.make_merged_blocks(map, old_owner_blocks.clone())?;
old_neighbourhood_blocks.sort_by_key(|block| block.perimeter.interior.len());
self.neighbourhoods.get_mut(&old_owner).unwrap().block =
old_neighbourhood_blocks.pop().unwrap();
let new_splits = !old_neighbourhood_blocks.is_empty();
for split_piece in old_neighbourhood_blocks {
let new_neighbourhood = NeighbourhoodID(self.neighbourhood_id_counter);
self.neighbourhood_id_counter += 1;
self.neighbourhoods
.insert(new_neighbourhood, NeighbourhoodInfo::new(split_piece));
}
if new_splits {
for id in old_owner_blocks {
self.block_to_neighbourhood
.insert(id, self.neighbourhood_containing(id).unwrap());
}
}
}
self.neighbourhoods.get_mut(&new_owner).unwrap().block = new_neighbourhood_block;
for id in add_all {
self.block_to_neighbourhood.insert(id, new_owner);
}
Ok(return_value)
}
pub fn remove_block_from_neighbourhood(
&mut self,
map: &Map,
id: BlockID,
) -> Result<Option<NeighbourhoodID>> {
let old_owner = self.block_to_neighbourhood(id);
let current_perim_set: BTreeSet<RoadSideID> = self.neighbourhoods[&old_owner]
.block
.perimeter
.roads
.iter()
.cloned()
.collect();
for road_side in &self.get_block(id).perimeter.roads {
if !current_perim_set.contains(road_side) {
continue;
}
let other_side = road_side.other_side();
if let Some((new_owner, _)) = self
.neighbourhoods
.iter()
.find(|(_, info)| info.block.perimeter.roads.contains(&other_side))
{
return self.transfer_blocks(map, vec![id], *new_owner);
}
}
let new_owner = NeighbourhoodID(self.neighbourhood_id_counter);
self.neighbourhood_id_counter += 1;
self.neighbourhoods.insert(
new_owner,
NeighbourhoodInfo::new(self.get_block(id).clone()),
);
let result = self.transfer_blocks(map, vec![id], new_owner);
if result.is_err() {
self.neighbourhoods.remove(&new_owner).unwrap();
}
result
}
}
impl Partitioning {
pub fn neighbourhood_block(&self, id: NeighbourhoodID) -> &Block {
&self.neighbourhoods[&id].block
}
pub fn neighbourhood_area_km2(&self, id: NeighbourhoodID) -> String {
let area = if let Some(ref custom) = self.custom_boundaries.get(&id) {
custom.boundary_polygon.area()
} else {
self.neighbourhood_block(id).polygon.area()
};
let area = area / 1_000_000.0;
format!("~{:.1} km²", area)
}
pub fn get_info(&self, id: NeighbourhoodID) -> &NeighbourhoodInfo {
&self.neighbourhoods[&id]
}
pub fn override_neighbourhood_boundary_polygon(
&mut self,
id: NeighbourhoodID,
polygon: Polygon,
) {
self.neighbourhoods
.get_mut(&id)
.unwrap()
.override_drawing_boundary = Some(polygon);
}
pub fn add_custom_boundary(&mut self, custom: CustomBoundary) -> NeighbourhoodID {
let id = NeighbourhoodID(self.neighbourhood_id_counter);
self.neighbourhood_id_counter += 1;
self.custom_boundaries.insert(id, custom);
id
}
pub fn all_neighbourhoods(&self) -> &BTreeMap<NeighbourhoodID, NeighbourhoodInfo> {
&self.neighbourhoods
}
fn neighbourhood_containing(&self, find_block: BlockID) -> Option<NeighbourhoodID> {
let find_block = self.get_block(find_block);
for (id, info) in &self.neighbourhoods {
if info.block.perimeter.contains(&find_block.perimeter) {
return Some(*id);
}
}
None
}
pub fn all_single_blocks(&self) -> Vec<(BlockID, &Block)> {
self.single_blocks
.iter()
.enumerate()
.map(|(idx, block)| (BlockID(idx), block))
.collect()
}
pub fn all_block_ids(&self) -> Vec<BlockID> {
(0..self.single_blocks.len()).map(BlockID).collect()
}
pub fn get_block(&self, id: BlockID) -> &Block {
&self.single_blocks[id.0]
}
pub fn block_to_neighbourhood(&self, id: BlockID) -> NeighbourhoodID {
self.block_to_neighbourhood[&id]
}
pub fn neighbourhood_to_blocks(&self, id: NeighbourhoodID) -> BTreeSet<BlockID> {
let mut result = BTreeSet::new();
for (block, n) in &self.block_to_neighbourhood {
if *n == id {
result.insert(*block);
}
}
result
}
pub fn some_block_in_neighbourhood(&self, id: NeighbourhoodID) -> BlockID {
for (block, neighbourhood) in &self.block_to_neighbourhood {
if id == *neighbourhood {
return *block;
}
}
unreachable!("{:?} has no blocks", id);
}
pub fn calculate_frontier(&self, perim: &Perimeter) -> BTreeSet<BlockID> {
let perim_roads: BTreeSet<RoadID> = perim.roads.iter().map(|id| id.road).collect();
let mut frontier = BTreeSet::new();
for (block_id, block) in self.all_single_blocks() {
for road_side_id in &block.perimeter.roads {
if perim_roads.contains(&road_side_id.road) {
frontier.insert(block_id);
break;
}
}
}
frontier
}
fn adjacent_blocks(&self, id: BlockID) -> BTreeSet<BlockID> {
let mut blocks = self.calculate_frontier(&self.get_block(id).perimeter);
blocks.retain(|x| *x != id);
blocks
}
fn make_merged_blocks(&self, map: &Map, input: BTreeSet<BlockID>) -> Result<Vec<Block>> {
let mut perimeters = Vec::new();
for id in input {
perimeters.push(self.get_block(id).perimeter.clone());
}
let mut blocks = Vec::new();
let stepwise_debug = false;
for perim in Perimeter::merge_all(map, perimeters, stepwise_debug) {
blocks.push(perim.to_block(map)?);
}
Ok(blocks)
}
pub fn find_intermediate_blocks(
&self,
new_owner: NeighbourhoodID,
target_block: BlockID,
) -> Vec<BlockID> {
let adjacent_to_target_block = self.adjacent_blocks(target_block);
let _new_owner_frontier =
self.calculate_frontier(&self.neighbourhood_block(new_owner).perimeter);
let mut result = Vec::new();
for id in adjacent_to_target_block.clone() {
if self.block_to_neighbourhood[&id] == new_owner {
continue;
}
if self
.adjacent_blocks(id)
.into_iter()
.all(|x| x == target_block || adjacent_to_target_block.contains(&x))
{
result.push(id);
}
}
result
}
}