wiki-substitution-tiling.rs

1use figures::{ink, save, Board, Frame};2use mrlyrs::core::error::Result;34const DEPTH: usize = 3;5const GAPS: [f64; DEPTH] = [22.0, 11.0, 4.0];67#[derive(Clone, Copy)]8struct Chair {9    x: f64,10    y: f64,11    side: f64,12    turn: usize,13}1415fn spin(p: (f64, f64), centre: (f64, f64), turn: usize) -> (f64, f64) {16    let (mut dx, mut dy) = (p.0 - centre.0, p.1 - centre.1);17    for _ in 0..turn % 4 {18        (dx, dy) = (-dy, dx);19    }20    (centre.0 + dx, centre.1 + dy)21}2223fn outline(c: Chair) -> Vec<(f64, f64)> {24    let (s, h) = (c.side, c.side / 2.0);25    let centre = (c.x + h, c.y + h);26    [(0.0, 0.0), (s, 0.0), (s, h), (h, h), (h, s), (0.0, s)]27        .iter()28        .map(|&(u, v)| spin((c.x + u, c.y + v), centre, c.turn))29        .collect()30}3132fn inflate(c: Chair) -> [Chair; 4] {33    let h = c.side / 2.0;34    let q = c.side / 4.0;35    let centre = (c.x + h, c.y + h);36    let place = |x: f64, y: f64, turn: usize| {37        let mid = spin((c.x + x + q, c.y + y + q), centre, c.turn);38        Chair {39            x: mid.0 - q,40            y: mid.1 - q,41            side: h,42            turn: (c.turn + turn) % 4,43        }44    };45    [46        place(0.0, 0.0, 0),47        place(q, q, 0),48        place(h, 0.0, 1),49        place(0.0, h, 3),50    ]51}5253fn area(c: Chair) -> f64 {54    0.75 * c.side * c.side55}5657fn main() -> Result<()> {58    let mut board = Board::square();59    let frame: Frame = board.frame(0.08);60    let root = Chair {61        x: 0.0,62        y: 0.0,63        side: 1.0,64        turn: 0,65    };66    let mut levels = vec![vec![root]];67    for _ in 0..DEPTH {68        let next: Vec<Chair> = levels69            .last()70            .unwrap()71            .iter()72            .flat_map(|c| inflate(*c))73            .collect();74        levels.push(next);75    }76    let counts: Vec<usize> = levels.iter().map(Vec::len).collect();77    assert_eq!(counts, vec![1, 4, 16, 64]);78    let leaves = levels.last().unwrap();79    let total: f64 = leaves.iter().map(|c| area(*c)).sum();80    assert!((total - area(root)).abs() < 1e-12);81    let mut cells = std::collections::HashSet::new();82    let grain = 2.0 / leaves[0].side;83    for c in leaves {84        let h = c.side / 2.0;85        for (u, v) in [(0.25, 0.25), (0.75, 0.25), (0.25, 0.75), (0.75, 0.75)] {86            let p = spin(87                (c.x + u * c.side, c.y + v * c.side),88                (c.x + h, c.y + h),89                c.turn,90            );91            let inside = !(u > 0.5 && v > 0.5);92            if inside {93                assert!(cells.insert(((p.0 * grain).floor() as i64, (p.1 * grain).floor() as i64)));94            }95        }96    }97    assert_eq!(cells.len(), 3 * 64);98    assert!(cells99        .iter()100        .all(|&(i, j)| (0..16).contains(&i) && (0..16).contains(&j) && (i < 8 || j < 8)));101    let even = leaves.iter().filter(|c| c.turn.is_multiple_of(2)).count();102    assert_eq!((even, leaves.len() - even), (32, 32));103104    let map = |p: (f64, f64)| (frame.x + p.0 * frame.w, frame.y + (1.0 - p.1) * frame.h);105    for c in leaves {106        let pts: Vec<(f64, f64)> = outline(*c).into_iter().map(map).collect();107        let color = if c.turn.is_multiple_of(2) {108            ink::blue()109        } else {110            ink::yellow()111        };112        board.polygon(&pts, color);113    }114    for depth in (1..=DEPTH).rev() {115        for c in &levels[depth] {116            let pts: Vec<(f64, f64)> = outline(*c).into_iter().map(map).collect();117            let gap = GAPS[depth - 1];118            for (i, a) in pts.iter().enumerate() {119                let b = pts[(i + 1) % pts.len()];120                let (x, y) = (a.0.min(b.0) - gap / 2.0, a.1.min(b.1) - gap / 2.0);121                let (w, h) = ((a.0 - b.0).abs() + gap, (a.1 - b.1).abs() + gap);122                board.rect(x, y, w, h, ink::ground());123            }124        }125    }126    save("wiki-substitution-tiling", &board)?;127    Ok(())128}