cartography 0.10.0

//! Ring stitching for multipolygon relations
//!
//! When OSM ways are split across PBF tile boundaries or simply fragmented,
//! they need to be stitched together by matching endpoints to form closed rings.

use geo::{Coord, LineString};
use std::collections::HashSet;

/// Stitch a collection of LineStrings into closed LineStrings (rings) by matching endpoints.
///
/// This function takes a set of line segments (ways) and attempts to connect them
/// into closed rings by finding shared endpoints. It handles fragmented rings where
/// ways are connected end-to-end.
///
/// # Returns
/// A vector of closed LineStrings (forming rings), or an error if stitching fails.
pub fn stitch_rings(ways: Vec<LineString>) -> Result<Vec<LineString>, String>
{
  if ways.is_empty()
  {
    return Err("No ways provided for stitching".to_string());
  }

  if ways.len() == 1
  {
    let way = &ways[0];
    if way.0.is_empty()
    {
      return Err("Empty LineString".to_string());
    }
    if way.0.first() == way.0.last()
    {
      return Ok(vec![way.clone()]);
    }
    return Err("Single way is not closed".to_string());
  }

  let mut rings = Vec::new();
  let mut remaining: HashSet<usize> = (0..ways.len()).collect();

  while !remaining.is_empty()
  {
    let start_idx = *remaining.iter().next().unwrap();
    let mut ring_coords: Vec<Coord> = ways[start_idx].0.clone();
    remaining.remove(&start_idx);

    loop
    {
      let last_coord = *ring_coords.last().unwrap();

      let mut found = false;
      let mut next_idx = None;
      let mut reverse = false;

      for &idx in &remaining
      {
        let way = &ways[idx];
        if way.0.is_empty()
        {
          continue;
        }
        let way_start = way.0[0];
        let way_end = way.0[way.0.len() - 1];

        if way_start == last_coord
        {
          next_idx = Some(idx);
          reverse = false;
          found = true;
          break;
        }
        if way_end == last_coord
        {
          next_idx = Some(idx);
          reverse = true;
          found = true;
          break;
        }
      }

      if !found
      {
        if ring_coords[0] == last_coord
        {
          rings.push(LineString::new(ring_coords));
          break;
        }
        else
        {
          return Err(format!(
            "Cannot stitch ring: ended at {:?}, needs to close back to {:?}",
            last_coord, ring_coords[0]
          ));
        }
      }

      let idx = next_idx.unwrap();
      let mut way_coords = ways[idx].0.clone();

      if reverse
      {
        way_coords.reverse();
      }

      if !way_coords.is_empty()
      {
        way_coords.remove(0);
      }

      ring_coords.extend(way_coords);
      remaining.remove(&idx);
    }
  }

  if rings.is_empty()
  {
    return Err("No rings were stitched".to_string());
  }

  Ok(rings)
}

#[cfg(test)]
mod tests
{
  use super::*;

  #[test]
  fn stitch_single_closed_ring()
  {
    let coords = vec![
      Coord { x: 0.0, y: 0.0 },
      Coord { x: 1.0, y: 0.0 },
      Coord { x: 1.0, y: 1.0 },
      Coord { x: 0.0, y: 1.0 },
      Coord { x: 0.0, y: 0.0 },
    ];
    let way = LineString::new(coords);
    let rings = stitch_rings(vec![way]).expect("Should stitch single closed ring");
    assert_eq!(rings.len(), 1);
  }

  #[test]
  fn stitch_fragmented_ring()
  {
    let way1 = LineString::new(vec![
      Coord { x: 0.0, y: 0.0 },
      Coord { x: 1.0, y: 0.0 },
      Coord { x: 1.0, y: 1.0 },
    ]);
    let way2 = LineString::new(vec![
      Coord { x: 1.0, y: 1.0 },
      Coord { x: 0.0, y: 1.0 },
      Coord { x: 0.0, y: 0.0 },
    ]);
    let rings = stitch_rings(vec![way1, way2]).expect("Should stitch fragmented ring");
    assert_eq!(rings.len(), 1);
  }

  #[test]
  fn stitch_fragmented_reversed()
  {
    let way1 = LineString::new(vec![
      Coord { x: 0.0, y: 0.0 },
      Coord { x: 1.0, y: 0.0 },
      Coord { x: 1.0, y: 1.0 },
    ]);
    let way2 = LineString::new(vec![
      Coord { x: 0.0, y: 0.0 },
      Coord { x: 0.0, y: 1.0 },
      Coord { x: 1.0, y: 1.0 },
    ]);
    let rings = stitch_rings(vec![way1, way2]).expect("Should stitch fragmented ring (reversed)");
    assert_eq!(rings.len(), 1);
  }

  #[test]
  fn stitch_multiple_rings()
  {
    let outer = LineString::new(vec![
      Coord { x: 0.0, y: 0.0 },
      Coord { x: 2.0, y: 0.0 },
      Coord { x: 2.0, y: 2.0 },
      Coord { x: 0.0, y: 2.0 },
      Coord { x: 0.0, y: 0.0 },
    ]);

    let inner = LineString::new(vec![
      Coord { x: 0.5, y: 0.5 },
      Coord { x: 1.5, y: 0.5 },
      Coord { x: 1.5, y: 1.5 },
      Coord { x: 0.5, y: 1.5 },
      Coord { x: 0.5, y: 0.5 },
    ]);

    let rings = stitch_rings(vec![outer, inner]).expect("Should stitch multiple rings");
    assert_eq!(rings.len(), 2);
  }
}