pub mod cell;
pub mod sweep;
use alloc::vec::Vec;
use crate::geom::Point2D;
use cell::SideIndex;
pub use cell::{Cell, CellId, Portal, PortalId};
#[derive(Clone, Debug, Default)]
pub struct Decomposition {
working: cell::Working,
pub(crate) xs: Vec<f64>,
pub(crate) slab_cells: Vec<CellId>,
pub(crate) slab_cell_offsets: Vec<u32>,
pub(crate) cells: Vec<Cell>,
pub(crate) portals: Vec<Portal>,
pub(crate) right_index: SideIndex,
pub(crate) left_index: SideIndex,
}
impl Decomposition {
pub fn empty() -> Self {
Self::default()
}
pub fn build_from_parts(&mut self, xs: Vec<f64>, cells: Vec<Cell>, portals: Vec<Portal>) {
self.clear();
self.xs = xs;
self.slab_cells.clear();
self.slab_cell_offsets.clear();
self.cells = cells;
self.portals = portals;
self.right_index.refill_from_portals(self.cells.len(), &self.portals, true, &mut self.working.cursor);
self.left_index.refill_from_portals(self.cells.len(), &self.portals, false, &mut self.working.cursor);
}
pub(crate) fn clear(&mut self) {
self.xs.clear();
self.slab_cells.clear();
self.slab_cell_offsets.clear();
self.cells.clear();
self.portals.clear();
self.right_index.clear();
self.left_index.clear();
}
#[inline]
pub fn cells(&self) -> &[Cell] {
&self.cells
}
#[inline]
pub fn portals(&self) -> &[Portal] {
&self.portals
}
#[inline]
pub fn cell_count(&self) -> usize {
self.cells.len()
}
#[inline]
pub fn portal_count(&self) -> usize {
self.portals.len()
}
pub fn slab_run(&self, k: usize) -> (usize, usize) {
let lo = if k == 0 { 0 } else { self.slab_cell_offsets[k - 1] as usize };
let hi = if k < self.slab_cell_offsets.len() {
self.slab_cell_offsets[k] as usize
} else {
self.slab_cells.len()
};
(lo, hi)
}
#[inline]
pub fn right_portals(&self, cell: CellId) -> &[PortalId] {
self.right_index.get(cell)
}
#[inline]
pub fn left_portals(&self, cell: CellId) -> &[PortalId] {
self.left_index.get(cell)
}
pub fn right_neighbours(&self, cell: CellId) -> impl Iterator<Item = (PortalId, CellId)> + '_ {
self.right_portals(cell)
.iter()
.map(move |p| (*p, self.portals[*p as usize].right))
}
pub fn left_neighbours(&self, cell: CellId) -> impl Iterator<Item = (PortalId, CellId)> + '_ {
self.left_portals(cell)
.iter()
.map(move |p| (*p, self.portals[*p as usize].left))
}
pub fn locate(&self, p: Point2D) -> Option<CellId> {
if !self.xs.is_empty() {
let k = slab_index(&self.xs, p.x)?;
let (lo, hi) = self.slab_run(k);
for &id in &self.slab_cells[lo..hi] {
let cell = &self.cells[id as usize];
let (lo, hi) = cell.y_range_at(p.x);
if p.y >= lo && p.y <= hi && cell.contains(p) {
return Some(id);
}
}
}
None
}
}
pub(crate) fn slab_index(xs: &[f64], x: f64) -> Option<usize> {
if xs.len() < 2 || x < xs[0] || x > xs[xs.len() - 1] {
return None;
}
let mut lo = 0usize;
let mut hi = xs.len() - 1;
while lo + 1 < hi {
let mid = (lo + hi) / 2;
if xs[mid] <= x {
lo = mid;
} else {
hi = mid;
}
}
Some(lo.min(xs.len() - 2))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::geom::Point2D;
use alloc::vec;
#[test]
fn slab_index_finds_the_right_slab() {
let xs = vec![0.0, 1.0, 2.0, 3.0];
assert_eq!(slab_index(&xs, 0.0), Some(0));
assert_eq!(slab_index(&xs, 0.5), Some(0));
assert_eq!(slab_index(&xs, 1.0), Some(1));
assert_eq!(slab_index(&xs, 1.5), Some(1));
assert_eq!(slab_index(&xs, 2.5), Some(2));
assert_eq!(slab_index(&xs, 3.0), Some(2));
assert_eq!(slab_index(&xs, 3.5), None);
assert_eq!(slab_index(&xs, -0.5), None);
}
#[test]
fn slab_index_of_a_degenerate_decomposition() {
assert_eq!(slab_index(&[], 0.0), None);
assert_eq!(slab_index(&[0.0], 0.0), None);
}
#[test]
fn locate_on_an_empty_decomposition_is_none() {
let d = Decomposition::default();
assert_eq!(d.locate(Point2D::new(1.0, 1.0)), None);
assert_eq!(d.cell_count(), 0);
assert_eq!(d.portal_count(), 0);
assert!(d.cells().is_empty());
}
}