From dd2336f76bfaff01ccb5b57f4453629ff62016b3 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 2 May 2020 13:57:30 -0400 Subject: frontier/min: Implement min selection --- src/frontier/min.rs | 150 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 150 insertions(+) create mode 100644 src/frontier/min.rs (limited to 'src/frontier') diff --git a/src/frontier/min.rs b/src/frontier/min.rs new file mode 100644 index 0000000..b22b290 --- /dev/null +++ b/src/frontier/min.rs @@ -0,0 +1,150 @@ +//! Minimum selection frontier. + +use super::{neighbors, Frontier, Pixel}; + +use crate::color::{ColorSpace, Rgb8}; +use crate::metric::soft::SoftKdForest; +use crate::metric::NearestNeighbors; + +use rand::Rng; + +use std::rc::Rc; + +/// A pixel on a min frontier. +#[derive(Debug)] +struct MinPixel { + pixel: Option>>, + filled: bool, +} + +impl MinPixel { + fn new() -> Self { + Self { + pixel: None, + filled: false, + } + } +} + +/// A [Frontier] that places colors on a neighbor of the closest pixel so far. +#[derive(Debug)] +pub struct MinFrontier { + rng: R, + pixels: Vec>, + forest: SoftKdForest>>, + width: u32, + height: u32, + x0: u32, + y0: u32, + len: usize, + deleted: usize, +} + +impl MinFrontier { + /// Create a MinFrontier with the given dimensions and initial pixel location. + pub fn new(rng: R, width: u32, height: u32, x0: u32, y0: u32) -> Self { + let size = (width as usize) * (height as usize); + let mut pixels = Vec::with_capacity(size); + for _ in 0..size { + pixels.push(MinPixel::new()); + } + + Self { + rng, + pixels, + forest: SoftKdForest::new(), + width, + height, + x0, + y0, + len: 0, + deleted: 0, + } + } + + fn pixel_index(&self, x: u32, y: u32) -> usize { + debug_assert!(x < self.width); + debug_assert!(y < self.height); + + (x + y * self.width) as usize + } + + fn free_neighbor(&mut self, x: u32, y: u32) -> Option<(u32, u32)> { + // Pick a pseudo-random neighbor + let offset: usize = self.rng.gen(); + + let neighbors = neighbors(x, y); + for i in 0..8 { + let (x, y) = neighbors[(i + offset) % 8]; + if x < self.width && y < self.height { + let i = self.pixel_index(x, y); + if !self.pixels[i].filled { + return Some((x, y)); + } + } + } + + None + } + + fn fill(&mut self, x: u32, y: u32, color: C) -> Option<(u32, u32)> { + let i = self.pixel_index(x, y); + let pixel = &mut self.pixels[i]; + if pixel.filled { + return None; + } + + let rc = Rc::new(Pixel::new(x, y, color)); + pixel.pixel = Some(rc.clone()); + pixel.filled = true; + + if self.free_neighbor(x, y).is_some() { + self.forest.push(rc); + self.len += 1; + } + + for &(x, y) in &neighbors(x, y) { + if x < self.width && y < self.height && self.free_neighbor(x, y).is_none() { + let i = self.pixel_index(x, y); + if let Some(pixel) = self.pixels[i].pixel.take() { + pixel.delete(); + self.deleted += 1; + } + } + } + + if 2 * self.deleted >= self.len { + self.forest.rebuild(); + self.len -= self.deleted; + self.deleted = 0; + } + + Some((x, y)) + } +} + +impl Frontier for MinFrontier { + fn width(&self) -> u32 { + self.width + } + + fn height(&self) -> u32 { + self.height + } + + fn len(&self) -> usize { + self.len - self.deleted + } + + fn place(&mut self, rgb8: Rgb8) -> Option<(u32, u32)> { + let color = C::from(rgb8); + let (x, y) = self + .forest + .nearest(&color) + .map(|n| n.item.pos) + .map(|(x, y)| self.free_neighbor(x, y).unwrap()) + .unwrap_or((self.x0, self.y0)); + + self.fill(x, y, color) + } +} -- cgit v1.2.3