frontier/min: Implement min selection

2 files changed, 211 insertions, 0 deletions

diff --git a/src/frontier.rs b/src/frontier.rs
index 1c5a173..e1b6528 100644
--- a/src/frontier.rs
+++ b/src/frontier.rs
@@ -1,6 +1,7 @@
 //! Frontiers on which to place pixels.
 
 pub mod image;
+pub mod min;
 
 use crate::color::{ColorSpace, Rgb8};
 use crate::metric::kd::Cartesian;
@@ -8,6 +9,7 @@ use crate::metric::soft::SoftDelete;
 use crate::metric::Metric;
 
 use std::cell::Cell;
+use std::rc::Rc;
 
 /// A frontier of pixels.
 pub trait Frontier {
@@ -85,3 +87,62 @@ impl<C> SoftDelete for Pixel<C> {
         self.deleted.get()
     }
 }
+
+impl<C: Metric<[f64]>> Metric<[f64]> for Rc<Pixel<C>> {
+    type Distance = C::Distance;
+
+    fn distance(&self, other: &[f64]) -> Self::Distance {
+        (**self).distance(other)
+    }
+}
+
+impl<C: Metric> Metric<Rc<Pixel<C>>> for C {
+    type Distance = C::Distance;
+
+    fn distance(&self, other: &Rc<Pixel<C>>) -> Self::Distance {
+        self.distance(&other.color)
+    }
+}
+
+impl<C: Metric> Metric for Rc<Pixel<C>> {
+    type Distance = C::Distance;
+
+    fn distance(&self, other: &Self) -> Self::Distance {
+        (**self).distance(&**other)
+    }
+}
+
+impl<C: Cartesian> Cartesian for Rc<Pixel<C>> {
+    fn dimensions(&self) -> usize {
+        (**self).dimensions()
+    }
+
+    fn coordinate(&self, i: usize) -> f64 {
+        (**self).coordinate(i)
+    }
+}
+
+impl<C> SoftDelete for Rc<Pixel<C>> {
+    fn is_deleted(&self) -> bool {
+        (**self).is_deleted()
+    }
+}
+
+/// Return all the neighbors of a pixel location.
+fn neighbors(x: u32, y: u32) -> [(u32, u32); 8] {
+    let xm1 = x.wrapping_sub(1);
+    let ym1 = y.wrapping_sub(1);
+    let xp1 = x + 1;
+    let yp1 = y + 1;
+
+    [
+        (xm1, ym1),
+        (xm1, y),
+        (xm1, yp1),
+        (x, ym1),
+        (x, yp1),
+        (xp1, ym1),
+        (xp1, y),
+        (xp1, yp1),
+    ]
+}
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<C> {
+    pixel: Option<Rc<Pixel<C>>>,
+    filled: bool,
+}
+
+impl<C: ColorSpace> MinPixel<C> {
+    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<C, R> {
+    rng: R,
+    pixels: Vec<MinPixel<C>>,
+    forest: SoftKdForest<Rc<Pixel<C>>>,
+    width: u32,
+    height: u32,
+    x0: u32,
+    y0: u32,
+    len: usize,
+    deleted: usize,
+}
+
+impl<C: ColorSpace, R: Rng> MinFrontier<C, R> {
+    /// 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<C: ColorSpace, R: Rng> Frontier for MinFrontier<C, R> {
+    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)
+    }
+}