wiki-euler-characteristic.rs

1use mrlycore::errors::Result;2use mrlyfig::{ink, iso, save, Board, Frame, Grid};3use mrlymath::two::{census, designs};45const SIDE: usize = 9;67fn corner(i: usize) -> (f64, f64, f64) {8    ((i & 1) as f64, ((i >> 1) & 1) as f64, ((i >> 2) & 1) as f64)9}1011fn cube(board: &mut Board, frame: Frame) -> (usize, usize, usize) {12    let flat: Vec<(f64, f64)> = (0..8)13        .map(|i| {14            let (x, y, z) = corner(i);15            iso::project(x, y, z)16        })17        .collect();18    let mut lo = (f64::MAX, f64::MAX);19    let mut hi = (f64::MIN, f64::MIN);20    for p in &flat {21        lo.0 = lo.0.min(p.0);22        lo.1 = lo.1.min(p.1);23        hi.0 = hi.0.max(p.0);24        hi.1 = hi.1.max(p.1);25    }26    let span = (hi.0 - lo.0).max(hi.1 - lo.1);27    let scale = frame.w.min(frame.h) * 0.95 / span;28    let (cx, cy) = frame.center();29    let place = |p: (f64, f64)| {30        (31            cx + (p.0 - (lo.0 + hi.0) / 2.0) * scale,32            cy + (p.1 - (lo.1 + hi.1) / 2.0) * scale,33        )34    };3536    let faces = [[4usize, 5, 7, 6], [1, 3, 7, 5], [2, 3, 7, 6]];37    let tones = [38        ink::blue(),39        ink::mix(ink::blue(), ink::ground(), 0.3),40        ink::mix(ink::blue(), ink::ground(), 0.55),41    ];42    for (quad, tone) in faces.iter().zip(tones) {43        let pts: Vec<(f64, f64)> = quad.iter().map(|i| place(flat[*i])).collect();44        board.polygon(&pts, tone);45    }4647    let mut edges = 0usize;48    for a in 0..8usize {49        for b in a + 1..8usize {50            if (a ^ b).count_ones() != 1 {51                continue;52            }53            let hidden = a == 0 || b == 0;54            board.segment(55                place(flat[a]),56                place(flat[b]),57                if hidden { 4.0 } else { 7.0 },58                if hidden { ink::dim() } else { ink::fg() },59            );60            edges += 1;61        }62    }63    for p in &flat {64        let (x, y) = place(*p);65        board.disc(x, y, 15.0, ink::yellow());66    }67    (8, edges, faces.len() * 2)68}6970fn holes(board: &mut Board, frame: Frame) -> Result<usize> {71    let carpet = designs::carpet(3, 2)?;72    assert_eq!(carpet.width(), SIDE);73    let grid = Grid::new(frame, SIDE, SIDE, 0.0);74    grid.paint(board, &carpet, |kind| {75        (kind != 0).then_some(ink::blue())76    });7778    let mut seen = [[false; SIDE]; SIDE];79    let mut found = 0usize;80    for row in 0..SIDE {81        for col in 0..SIDE {82            if seen[row][col] || carpet.types().get(&[row, col]) != 0 {83                continue;84            }85            let mut stack = vec![(row, col)];86            let mut cells = Vec::new();87            seen[row][col] = true;88            while let Some((r, c)) = stack.pop() {89                cells.push((r, c));90                let step = |r: usize, c: usize, stack: &mut Vec<(usize, usize)>, seen: &mut [[bool; SIDE]; SIDE]| {91                    if !seen[r][c] && carpet.types().get(&[r, c]) == 0 {92                        seen[r][c] = true;93                        stack.push((r, c));94                    }95                };96                if r > 0 {97                    step(r - 1, c, &mut stack, &mut seen);98                }99                if r + 1 < SIDE {100                    step(r + 1, c, &mut stack, &mut seen);101                }102                if c > 0 {103                    step(r, c - 1, &mut stack, &mut seen);104                }105                if c + 1 < SIDE {106                    step(r, c + 1, &mut stack, &mut seen);107                }108            }109            let rows: Vec<usize> = cells.iter().map(|(r, _)| *r).collect();110            let cols: Vec<usize> = cells.iter().map(|(_, c)| *c).collect();111            let (r0, r1) = (*rows.iter().min().unwrap(), *rows.iter().max().unwrap());112            let (c0, c1) = (*cols.iter().min().unwrap(), *cols.iter().max().unwrap());113            let (x0, y0, _, _) = grid.cell(c0, r0);114            let (x1, y1, w, h) = grid.cell(c1, r1);115            let cx = (x0 + x1 + w) / 2.0;116            let cy = (y0 + y1 + h) / 2.0;117            let radius = ((x1 + w - x0).min(y1 + h - y0)) * 0.62;118            board.ring(cx, cy, radius, 6.0, ink::orange());119            found += 1;120        }121    }122    Ok(found)123}124125fn main() -> Result<()> {126    let mut board = Board::square();127    let area = board.frame(0.06);128    let panes = area.cols(2);129    let (vertices, edges, faces) = cube(&mut board, panes[0].square().inset(18.0));130    assert_eq!((vertices, edges, faces), (8, 12, 6));131    assert_eq!(vertices as i64 - edges as i64 + faces as i64, 2);132    let found = holes(&mut board, panes[1].square().inset(18.0))?;133    assert_eq!(found, 9);134    assert_eq!(census::euler(&designs::carpet(3, 2)?)?, 1 - found as i64);135    assert_eq!(census::euler(&designs::carpet(3, 3)?)?, -72);136    save("wiki-euler-characteristic", &board)?;137    Ok(())138}