Skip to content

armgit / klad

Public Imported from GitHub
0

A drawing app built for agent/human collaboration

Rust
23.7 KB
Raw Blame
use crate::color::{Rgba, to_oklab};
use crate::pixel::Grid;
use serde::Serialize;
use std::collections::{BTreeMap, BTreeSet};

const ARM: u32 = 2;
const BAND: u32 = 4;
const STEP: u32 = 2;

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize)]
#[serde(rename_all = "kebab-case")]
pub enum Kind {
    Stray,
    Corner,
    Jagged,
    Banding,
    OffPalette,
}

impl Kind {
    pub const ALL: [Kind; 5] = [Kind::Stray, Kind::Corner, Kind::Jagged, Kind::Banding, Kind::OffPalette];

    pub fn name(self) -> &'static str {
        match self {
            Kind::Stray => "stray pixel",
            Kind::Corner => "doubled corner",
            Kind::Jagged => "jagged line",
            Kind::Banding => "banding",
            Kind::OffPalette => "off the palette",
        }
    }

    pub fn advice(self) -> &'static str {
        match self {
            Kind::Stray => {
                "a single pixel with no neighbour of its colour: keep it if it is a detail, else join it to a cluster or remove it"
            }
            Kind::Corner => "an L in a one-pixel line, which reads as a thick spot: remove the corner pixel",
            Kind::Jagged => "a short run between longer ones breaks the line's rhythm: even out the run lengths",
            Kind::Banding => {
                "a one-pixel band that follows the edge next to it: break it up, or let the shade form its own shape"
            }
            Kind::OffPalette => {
                "pixels in a colour the palette does not hold: recolour them to a palette colour, or add the colour"
            }
        }
    }
}

#[derive(Clone, Debug, PartialEq, Serialize)]
pub struct Finding {
    pub kind: Kind,
    pub at: [u32; 2],
    pub to: [u32; 2],
    pub key: String,
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub beside: Vec<String>,
    pub note: String,
    #[serde(default, skip_serializing_if = "std::ops::Not::not")]
    pub minor: bool,
}

type Cell = (i64, i64);

const AROUND: [Cell; 8] = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)];

struct Field<'a> {
    grid: &'a Grid,
    wrap: bool,
}

impl<'a> Field<'a> {
    fn at(&self, (x, y): Cell) -> Option<&'a str> {
        let (w, h) = (self.grid.width as i64, self.grid.height as i64);
        let (x, y) = match self.wrap {
            true => (x.rem_euclid(w.max(1)), y.rem_euclid(h.max(1))),
            false => (x, y),
        };
        match x >= 0 && y >= 0 && x < w && y < h {
            true => self.grid.at(x as u32, y as u32),
            false => None,
        }
    }

    fn is(&self, cell: Cell, key: &str) -> bool {
        self.at(cell) == Some(key)
    }

    fn same(&self, (x, y): Cell, key: &str) -> Vec<Cell> {
        AROUND
            .iter()
            .filter(|(dx, dy)| self.is((x + dx, y + dy), key))
            .copied()
            .collect()
    }

    fn arm(&self, (x, y): Cell, (dx, dy): Cell, key: &str) -> u32 {
        let most = self.grid.width.max(self.grid.height) as i64;
        (1..=most)
            .take_while(|n| self.is((x + dx * n, y + dy * n), key))
            .count() as u32
    }

    fn cells(&self) -> impl Iterator<Item = (Cell, &'a str)> + '_ {
        let (w, h) = (self.grid.width as i64, self.grid.height as i64);
        (0..h)
            .flat_map(move |y| (0..w).map(move |x| (x, y)))
            .filter_map(|cell| self.at(cell).map(|key| (cell, key)))
    }
}

fn place((x, y): Cell) -> [u32; 2] {
    [x.max(0) as u32, y.max(0) as u32]
}

fn strays(field: &Field) -> Vec<Finding> {
    field
        .cells()
        .filter(|(cell, key)| field.same(*cell, key).is_empty())
        .map(|(cell, key)| Finding {
            kind: Kind::Stray,
            at: place(cell),
            to: place(cell),
            key: key.to_string(),
            beside: Vec::new(),
            note: "alone: no neighbour of its colour".into(),
            minor: false,
        })
        .map(|found| settled(field, found))
        .collect()
}

fn settled(field: &Field, found: Finding) -> Finding {
    let cell = (found.at[0] as i64, found.at[1] as i64);
    let around: Vec<Option<&str>> = AROUND
        .iter()
        .map(|(dx, dy)| field.at((cell.0 + dx, cell.1 + dy)))
        .collect();
    let empty = around.iter().filter(|key| key.is_none()).count();
    let others: BTreeSet<&str> = around.iter().flatten().copied().collect();
    match (empty >= 5, others.len() == 1 && empty <= 3) {
        (true, _) => Finding {
            note: "alone, outside the shape".into(),
            ..found
        },
        (false, true) => Finding {
            beside: others.iter().map(|key| key.to_string()).collect(),
            note: "alone in a field of one colour".into(),
            ..found
        },
        (false, false) => Finding {
            note: "alone among other colours".into(),
            minor: true,
            ..found
        },
    }
}

fn elbow(field: &Field, cell: Cell, key: &str) -> Option<[Cell; 2]> {
    const BESIDE: [Cell; 4] = [(0, -1), (1, 0), (0, 1), (-1, 0)];
    let arms: Vec<Cell> = BESIDE
        .iter()
        .filter(|(dx, dy)| field.is((cell.0 + dx, cell.1 + dy), key))
        .copied()
        .collect();
    let [a, b] = arms.as_slice() else {
        return None;
    };
    let square = a.0 * b.0 + a.1 * b.1 == 0;
    let inside = (cell.0 + a.0 + b.0, cell.1 + a.1 + b.1);
    let meant = field.arm(cell, *a, key) >= ARM && field.arm(cell, *b, key) >= ARM;
    (square && !field.is(inside, key) && !meant).then_some([(cell.0 + a.0, cell.1 + a.1), (cell.0 + b.0, cell.1 + b.1)])
}

fn in_shading(field: &Field, cell: Cell, key: &str, colour: &dyn Fn(&str) -> Option<Rgba>) -> bool {
    let light = |key: &str| colour(key).map(|c| to_oklab(c)[0]);
    let Some(own) = light(key) else {
        return false;
    };
    AROUND
        .iter()
        .filter_map(|(dx, dy)| field.at((cell.0 + dx, cell.1 + dy)))
        .filter(|other| *other != key)
        .filter_map(light)
        .any(|other| other < own)
}

fn corners(field: &Field, colour: &dyn Fn(&str) -> Option<Rgba>) -> Vec<Finding> {
    field
        .cells()
        .filter(|(cell, key)| {
            let Some(arms) = elbow(field, *cell, key) else {
                return false;
            };
            let thin = field.same(*cell, key).len() <= 3;
            let alone = arms.iter().all(|arm| elbow(field, *arm, key).is_none());
            let goes_on = arms.iter().any(|arm| {
                field
                    .same(*arm, key)
                    .iter()
                    .map(|(dx, dy)| (arm.0 + dx, arm.1 + dy))
                    .any(|next| next != *cell && !arms.contains(&next))
            });
            thin && alone && goes_on
        })
        .map(|(cell, key)| Finding {
            kind: Kind::Corner,
            at: place(cell),
            to: place(cell),
            key: key.to_string(),
            beside: Vec::new(),
            note: "an L in a one-pixel line".into(),
            minor: false,
        })
        .map(|found| {
            let cell = (found.at[0] as i64, found.at[1] as i64);
            match in_shading(field, cell, &found.key, colour) {
                true => Finding {
                    note: "an L where two shades meet, not in a drawn line".into(),
                    minor: true,
                    ..found
                },
                false => found,
            }
        })
        .collect()
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Lie {
    Across,
    Down,
    Dot,
}

#[derive(Clone, Copy, Debug)]
struct Stretch {
    lie: Lie,
    first: Cell,
    last: Cell,
    length: u32,
}

fn chains(field: &Field, key: &str, cells: &[Cell]) -> Vec<Vec<Cell>> {
    let thin: BTreeSet<Cell> = cells
        .iter()
        .filter(|cell| {
            let same = field.same(**cell, key);
            same.len() <= 2
        })
        .copied()
        .collect();
    let next_of = |cell: Cell, seen: &BTreeSet<Cell>| -> Option<Cell> {
        let mut around: Vec<Cell> = AROUND
            .iter()
            .map(|(dx, dy)| (cell.0 + dx, cell.1 + dy))
            .filter(|c| thin.contains(c) && !seen.contains(c))
            .collect();
        around.sort_by_key(|c| ((c.0 - cell.0).abs() + (c.1 - cell.1).abs(), c.1, c.0));
        around.first().copied()
    };
    let ends: Vec<Cell> = thin
        .iter()
        .filter(|cell| {
            AROUND
                .iter()
                .filter(|(dx, dy)| thin.contains(&(cell.0 + dx, cell.1 + dy)))
                .count()
                <= 1
        })
        .copied()
        .collect();
    let mut seen: BTreeSet<Cell> = BTreeSet::new();
    let mut made = Vec::new();
    ends.iter().chain(thin.iter()).for_each(|start| {
        if seen.contains(start) {
            return;
        }
        let mut chain = vec![*start];
        seen.insert(*start);
        while let Some(next) = next_of(*chain.last().unwrap_or(start), &seen) {
            seen.insert(next);
            chain.push(next);
        }
        made.push(chain);
    });
    made
}

fn stretches(chain: &[Cell]) -> Vec<Stretch> {
    let mut made: Vec<Stretch> = Vec::new();
    chain.iter().for_each(|cell| {
        let joins = made.last().map(|run| {
            let (dx, dy) = (cell.0 - run.last.0, cell.1 - run.last.1);
            match (run.lie, dx.abs(), dy.abs()) {
                (Lie::Dot | Lie::Across, 1, 0) => Some(Lie::Across),
                (Lie::Dot | Lie::Down, 0, 1) => Some(Lie::Down),
                _ => None,
            }
        });
        match (joins, made.last_mut()) {
            (Some(Some(lie)), Some(run)) => {
                run.lie = lie;
                run.last = *cell;
                run.length += 1;
            }
            _ => made.push(Stretch {
                lie: Lie::Dot,
                first: *cell,
                last: *cell,
                length: 1,
            }),
        }
    });
    made
}

fn jagged(field: &Field) -> Vec<Finding> {
    let mut by_key: BTreeMap<&str, Vec<Cell>> = BTreeMap::new();
    field
        .cells()
        .for_each(|(cell, key)| by_key.entry(key).or_default().push(cell));
    by_key
        .iter()
        .flat_map(|(key, cells)| {
            chains(field, key, cells)
                .into_iter()
                .flat_map(|chain| {
                    let runs = stretches(&chain);
                    runs.windows(3)
                        .filter(|w| {
                            let (a, b, c) = (w[0], w[1], w[2]);
                            let lies = a.lie == c.lie && a.lie != Lie::Dot && (b.lie == a.lie || b.lie == Lie::Dot);
                            let along = |run: &Stretch| match a.lie {
                                Lie::Down => (run.last.1 - run.first.1).signum(),
                                _ => (run.last.0 - run.first.0).signum(),
                            };
                            let aside = |from: &Stretch, to: &Stretch| match a.lie {
                                Lie::Down => (to.first.0 - from.last.0).signum(),
                                _ => (to.first.1 - from.last.1).signum(),
                            };
                            let onward = along(&a) == along(&c) && (b.length == 1 || along(&b) == along(&a));
                            let one_way = aside(&a, &b) == aside(&b, &c) && aside(&a, &b) != 0;
                            lies && onward && one_way && b.length + STEP <= a.length && b.length + STEP <= c.length
                        })
                        .map(|w| Finding {
                            kind: Kind::Jagged,
                            at: place((w[1].first.0.min(w[1].last.0), w[1].first.1.min(w[1].last.1))),
                            to: place((w[1].first.0.max(w[1].last.0), w[1].first.1.max(w[1].last.1))),
                            key: key.to_string(),
                            beside: Vec::new(),
                            note: format!(
                                "a run of {} between runs of {} and {}",
                                w[1].length, w[0].length, w[2].length
                            ),
                            minor: false,
                        })
                        .collect::<Vec<_>>()
                })
                .collect::<Vec<_>>()
        })
        .collect()
}

fn banding(field: &Field, colour: &dyn Fn(&str) -> Option<Rgba>) -> Vec<Finding> {
    let light = |key: &str| colour(key).map(|c| to_oklab(c)[0]);
    let between = |a: &str, b: &str, c: &str| -> bool {
        match (light(a), light(b), light(c)) {
            (Some(la), Some(lb), Some(lc)) => (la < lb && lb < lc) || (la > lb && lb > lc),
            _ => false,
        }
    };
    let (w, h) = (field.grid.width as i64, field.grid.height as i64);
    let sides = |cell: Cell, down: bool| -> Option<(&str, &str, &str)> {
        let (before, after) = match down {
            true => ((cell.0 - 1, cell.1), (cell.0 + 1, cell.1)),
            false => ((cell.0, cell.1 - 1), (cell.0, cell.1 + 1)),
        };
        let (a, b, c) = (field.at(before)?, field.at(cell)?, field.at(after)?);
        (a != b && b != c && a != c).then_some((a, b, c))
    };
    let lines = |down: bool| -> Vec<Finding> {
        let (outer, inner) = match down {
            true => (w, h),
            false => (h, w),
        };
        (0..outer)
            .flat_map(|fixed| {
                let cell = move |moving: i64| match down {
                    true => (fixed, moving),
                    false => (moving, fixed),
                };
                let mut found: Vec<Finding> = Vec::new();
                let mut start = 0;
                while start < inner {
                    let Some(first) = sides(cell(start), down) else {
                        start += 1;
                        continue;
                    };
                    let length = (start..inner)
                        .take_while(|at| sides(cell(*at), down) == Some(first))
                        .count() as i64;
                    if length as u32 >= BAND && between(first.0, first.1, first.2) {
                        found.push(Finding {
                            kind: Kind::Banding,
                            at: place(cell(start)),
                            to: place(cell(start + length - 1)),
                            key: first.1.to_string(),
                            beside: vec![first.0.to_string(), first.2.to_string()],
                            note: format!("one pixel wide for {length} pixels"),
                            minor: false,
                        });
                    }
                    start += length;
                }
                found
            })
            .collect()
    };
    lines(false).into_iter().chain(lines(true)).collect()
}

fn off_palette(field: &Field) -> Vec<Finding> {
    let mut seen: BTreeMap<&str, (Cell, usize)> = BTreeMap::new();
    field
        .cells()
        .filter(|(_, key)| key.starts_with('#'))
        .for_each(|(cell, key)| seen.entry(key).or_insert((cell, 0)).1 += 1);
    seen.into_iter()
        .map(|(key, (first, count))| Finding {
            kind: Kind::OffPalette,
            at: place(first),
            to: place(first),
            key: key.to_string(),
            beside: Vec::new(),
            note: match count {
                1 => "1 pixel".to_string(),
                n => format!("{n} pixels, the first here"),
            },
            minor: false,
        })
        .collect()
}

pub fn check(grid: &Grid, wrap: bool, colour: &dyn Fn(&str) -> Option<Rgba>) -> Vec<Finding> {
    let field = Field { grid, wrap };
    let mut found: Vec<Finding> = strays(&field)
        .into_iter()
        .chain(corners(&field, colour))
        .chain(jagged(&field))
        .chain(banding(&field, colour))
        .chain(off_palette(&field))
        .collect();
    found.sort_by(|a, b| {
        a.kind
            .cmp(&b.kind)
            .then(a.minor.cmp(&b.minor))
            .then(a.at[1].cmp(&b.at[1]))
            .then(a.at[0].cmp(&b.at[0]))
    });
    found
}

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

    fn grid(rows: &[&str]) -> Grid {
        Grid {
            width: rows[0].chars().count() as u32,
            height: rows.len() as u32,
            cells: rows
                .iter()
                .flat_map(|row| row.chars())
                .map(|c| match c {
                    '.' => None,
                    '?' => Some("#ff00ff".to_string()),
                    other => Some(other.to_string()),
                })
                .collect(),
        }
    }

    fn shade(key: &str) -> Option<Rgba> {
        let v = match key {
            "a" => 0.1,
            "b" => 0.4,
            "c" => 0.8,
            "i" => 0.0,
            _ => 0.6,
        };
        Some([v, v, v, 1.0])
    }

    fn found(rows: &[&str], kind: Kind) -> Vec<([u32; 2], [u32; 2])> {
        check(&grid(rows), false, &shade)
            .into_iter()
            .filter(|f| f.kind == kind)
            .map(|f| (f.at, f.to))
            .collect()
    }

    #[test]
    fn a_pixel_with_no_neighbour_of_its_colour_is_stray() {
        let rows = ["i....", ".bb..", ".bb.i", "....."];
        assert_eq!(found(&rows, Kind::Stray), [([0, 0], [0, 0]), ([4, 2], [4, 2])]);
        assert!(found(&["ii", "ii"], Kind::Stray).is_empty());
        assert_eq!(
            check(&grid(&["i..", "...", "..i"]), true, &shade)
                .iter()
                .filter(|f| f.kind == Kind::Stray)
                .count(),
            0,
            "on a canvas that wraps the two corners touch"
        );
    }

    #[test]
    fn single_pixels_among_other_colours_and_corners_in_shading_are_small_findings() {
        let all = |rows: &[&str]| check(&grid(rows), false, &shade);
        let lone = |rows: &[&str]| -> Vec<(String, bool)> {
            all(rows)
                .into_iter()
                .filter(|f| f.kind == Kind::Stray)
                .map(|f| (f.note, f.minor))
                .collect()
        };
        assert_eq!(
            lone(&["i....", ".....", "....."]),
            [("alone, outside the shape".to_string(), false)]
        );
        assert_eq!(
            lone(&["bbbbb", "bbibb", "bbbbb"]),
            [("alone in a field of one colour".to_string(), false)],
            "a speck in a flat area stands out"
        );
        assert_eq!(
            lone(&["aabbb", "aaibb", "ccccc"]),
            [("alone among other colours".to_string(), true)],
            "a stud where colours meet is most likely a detail"
        );
        let shaded = ["cbbbb", "bccbb", "bbcbb", "bbbcb"];
        let corner: Vec<bool> = all(&shaded)
            .into_iter()
            .filter(|f| f.kind == Kind::Corner)
            .map(|f| f.minor)
            .collect();
        assert_eq!(corner, [true], "a light L beside a darker shade is shading, not a line");
        let drawn = ["ibbbb", "biibb", "bbibb", "bbbib"];
        let corner: Vec<bool> = all(&drawn)
            .into_iter()
            .filter(|f| f.kind == Kind::Corner)
            .map(|f| f.minor)
            .collect();
        assert_eq!(corner, [false], "the same L in the darkest colour is a drawn line");
        let sorted: Vec<bool> = all(&["i....", ".....", "aabbb", "aaibb", "ccccc"])
            .into_iter()
            .filter(|f| f.kind == Kind::Stray)
            .map(|f| f.minor)
            .collect();
        assert_eq!(sorted, [false, true], "what stands out comes first");
    }

    #[test]
    fn an_l_in_a_thin_line_is_a_doubled_corner_but_a_box_corner_is_not() {
        let slip = ["i....", ".ii..", "..i..", "...i."];
        assert_eq!(found(&slip, Kind::Corner), [([2, 1], [2, 1])]);
        let clean = ["i....", ".i...", "..i..", "...i."];
        assert!(found(&clean, Kind::Corner).is_empty());
        let stairs = ["ii...", ".ii..", "..ii.", "...ii"];
        assert!(
            found(&stairs, Kind::Corner).is_empty(),
            "steps all the way are a diagonal two pixels wide, not a slip"
        );
        let boxed = ["iiiii", "i...i", "i...i", "iiiii"];
        assert!(
            found(&boxed, Kind::Corner).is_empty(),
            "arms of two or more both ways are a corner that is meant"
        );
        let small = ["iiii", "i..i", "iiii"];
        assert!(found(&small, Kind::Corner).is_empty(), "also on a small box");
        let filled = ["iii", "iii"];
        assert!(found(&filled, Kind::Corner).is_empty());
        let hook = ["iiiii", "....i", "....."];
        assert_eq!(
            found(&hook, Kind::Corner),
            [([4, 0], [4, 0])],
            "a short arm is not a box"
        );
        let blob = ["ii.", "i..", "..."];
        assert!(
            found(&blob, Kind::Corner).is_empty(),
            "three pixels are a cluster, not a line"
        );
        let wedge = ["..iii", "iii..", "ii...", "i...."];
        assert!(
            found(&wedge, Kind::Corner).is_empty(),
            "the stepped edge of a shape is not a line"
        );
    }

    #[test]
    fn a_short_run_between_longer_ones_is_jagged() {
        let jag = ["iiii.........", "....i........", ".....iiii....", "............."];
        assert_eq!(found(&jag, Kind::Jagged), [([4, 1], [4, 1])]);
        let note = check(&grid(&jag), false, &shade)
            .into_iter()
            .find(|f| f.kind == Kind::Jagged)
            .unwrap()
            .note;
        assert_eq!(note, "a run of 1 between runs of 4 and 4");
        let even = ["iii......", "...iii...", "......iii"];
        assert!(found(&even, Kind::Jagged).is_empty());
        let arc = ["i........", ".i.......", "..ii.....", "....iiii.", "........i"];
        assert!(
            found(&arc, Kind::Jagged).is_empty(),
            "runs that grow along a curve are fine"
        );
        let steep = ["i..", "i..", "i..", "i..", ".i.", "..i", "..i", "..i", "..i"];
        assert_eq!(
            found(&steep, Kind::Jagged),
            [([1, 4], [1, 4])],
            "the same down a column"
        );
        let bump = ["iiii.iiii", "....i...."];
        assert!(
            found(&bump, Kind::Jagged).is_empty(),
            "a notch that comes back is not a step"
        );
    }

    #[test]
    fn a_one_pixel_band_between_a_darker_and_a_lighter_colour_is_banding() {
        let bands = ["aaaaaa", "bbbbbb", "cccccc"];
        assert_eq!(found(&bands, Kind::Banding), [([0, 1], [5, 1])]);
        let wide = ["aaaaaa", "bbbbbb", "bbbbbb", "cccccc"];
        assert!(
            found(&wide, Kind::Banding).is_empty(),
            "two pixels wide is a shape of its own"
        );
        let line = ["cccccc", "iiiiii", "cccccc"];
        assert!(
            found(&line, Kind::Banding).is_empty(),
            "a line through one colour is a detail"
        );
        let dark = ["bbbbbb", "iiiiii", "cccccc"];
        assert!(
            found(&dark, Kind::Banding).is_empty(),
            "darker than both sides is a line, not a step"
        );
        let short = ["aaa", "bbb", "ccc"];
        assert!(found(&short, Kind::Banding).is_empty());
        let edge = ["......", "bbbbbb", "cccccc"];
        assert!(
            found(&edge, Kind::Banding).is_empty(),
            "an outline next to nothing is not banding"
        );
        let down = ["abc", "abc", "abc", "abc"];
        assert_eq!(found(&down, Kind::Banding), [([1, 0], [1, 3])]);
    }

    #[test]
    fn colours_that_are_not_palette_entries_are_listed_once_with_their_count() {
        let rows = ["bb?", "b??", "bbb"];
        let all = check(&grid(&rows), false, &shade);
        let off: Vec<&Finding> = all.iter().filter(|f| f.kind == Kind::OffPalette).collect();
        assert_eq!(off.len(), 1);
        assert_eq!(
            (off[0].at, off[0].key.as_str(), off[0].note.as_str()),
            ([2, 0], "#ff00ff", "3 pixels, the first here")
        );
        assert!(
            check(&grid(&["bb", "bb"]), false, &shade).is_empty(),
            "a clean drawing has no findings"
        );
        assert_eq!(Kind::ALL.len(), 5);
        assert!(Kind::ALL.iter().all(|k| !k.name().is_empty() && !k.advice().is_empty()));
    }
}