tilezz 0.2.0

Utilities to work with perfect-precision polygonal tiles built on top of cyclotomic integer rings.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

//! Orientation-preserving plane isometries over a cyclotomic ring, and the
//! orbit / edge-gluing primitives built on them.
//!
//! An [`Iso`] is `x |-> x * unit(rot) + shift`: a rotation by `rot` ring units
//! about the origin followed by an exact ring-element translation. Rotations
//! only -- no reflections -- matching the single-chirality scope of the whole
//! tiling machinery (chiral aperiodic monotiles glue without mirror images).
//! The family is closed under composition and inverse, so every element of a
//! tiling's symmetry group is one `Iso` with an exact `shift`.

use crate::cyclotomic::IsRing;
use crate::util::gcd;

/// An orientation-preserving plane isometry: `x |-> x * unit(rot) + shift`.
/// `rot = 0` is a translation, `rot = turn/2` a half-turn; in a real tiling
/// only crystallographic orders (1, 2, 3, 4, 6) ever occur.
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct Iso<T> {
    /// Rotation in ring units (multiples of one full turn / `T::turn()`).
    pub rot: i8,
    pub shift: T,
}

impl<T: IsRing> Iso<T> {
    fn turn() -> i64 {
        T::turn() as i64
    }
    pub fn id() -> Self {
        Iso {
            rot: 0,
            shift: T::zero(),
        }
    }
    /// The unique orientation-preserving isometry that carries one directed
    /// unit edge onto another: it sends `src_start` to `dst_start` and rotates
    /// the source direction `src_dir` onto the destination direction `dst_dir`.
    ///
    /// This is the placement algebra shared by every "match an edge, recover the
    /// tile's pose" call site: `rot = dst_dir - src_dir` aligns the two edge
    /// directions, and `shift = dst_start - src_start * unit(rot)` then pins the
    /// rotated source start onto the destination start. Directions are ring unit
    /// indices (see `dir_of_unit`); to glue *anti-parallel* (a tile's edge onto
    /// a boundary edge traversed in reverse), pass the reversed destination edge
    /// -- its start is the far endpoint and its direction is `dst_dir + turn/2`.
    pub fn carrying(src_start: T, src_dir: i8, dst_start: T, dst_dir: i8) -> Iso<T> {
        let rot = (dst_dir as i64 - src_dir as i64).rem_euclid(Self::turn()) as i8;
        Iso {
            rot,
            shift: dst_start - src_start * T::unit(rot),
        }
    }
    /// Image of a point: rotate by `rot`, then translate by `shift`.
    pub fn pt(&self, x: T) -> T {
        x * T::unit(self.rot) + self.shift
    }
    /// `self` after `other` (function composition).
    pub fn after(&self, other: &Iso<T>) -> Iso<T> {
        Iso {
            rot: (self.rot as i64 + other.rot as i64).rem_euclid(Self::turn()) as i8,
            shift: other.shift * T::unit(self.rot) + self.shift,
        }
    }
    /// The inverse isometry.
    pub fn inv(&self) -> Iso<T> {
        let r = ((Self::turn() - self.rot as i64).rem_euclid(Self::turn())) as i8;
        Iso {
            rot: r,
            shift: -(self.shift * T::unit(r)),
        }
    }
    /// The placed polygon: every vertex of `base` mapped through `self`.
    pub fn tile(&self, base: &[T]) -> Vec<T> {
        base.iter().map(|&x| self.pt(x)).collect()
    }
    /// Float centroid of the placed polygon (for radius / centrality tests).
    pub fn centroid(&self, base: &[T]) -> (f64, f64) {
        let (mut sx, mut sy) = (0.0, 0.0);
        for p in base {
            let (x, y) = self.pt(*p).xy();
            sx += x;
            sy += y;
        }
        let k = base.len() as f64;
        (sx / k, sy / k)
    }
}

/// Direction index of a unit ring vector (`unit(d) == v`), if it is one.
pub(crate) fn dir_of_unit<T: IsRing>(v: T) -> Option<i8> {
    let turn = T::turn();
    (0..turn).find(|&d| T::unit(d) == v)
}

/// The orientation-preserving isometry placing the neighbour across edge `e`
/// when that neighbour presents its own edge `f`: it maps the tile's directed
/// edge `f` onto edge `e` reversed (`p_f -> p_{e+1}`, `p_{f+1} -> p_e`).
/// `None` if the edges are not unit vectors of the ring.
pub(crate) fn gluing_iso<T: IsRing>(verts: &[T], e: usize, f: usize) -> Option<Iso<T>> {
    let n = verts.len();
    let turn = T::turn() as i64;
    let half = (turn / 2) as i8;
    let de = dir_of_unit(verts[(e + 1) % n] - verts[e])?;
    let df = dir_of_unit(verts[(f + 1) % n] - verts[f])?;
    // Carry the tile's directed edge f onto edge e *reversed*: source
    // `verts[f] -> verts[f+1]` onto destination `verts[e+1] -> verts[e]`, whose
    // start is `verts[e+1]` and whose direction is `de` flipped by a half turn.
    let dst_dir = (de as i64 + half as i64).rem_euclid(turn) as i8;
    Some(Iso::carrying(verts[f], df, verts[(e + 1) % n], dst_dir))
}

/// Rotation order of `rot` units, or `None` if non-crystallographic
/// (order not in {1,2,3,4,6} -- those can't be tiling rotation centres).
pub(crate) fn cryst_order<T: IsRing>(rot: i8) -> Option<usize> {
    let turn = T::turn() as i64;
    let ord = (turn / gcd(rot as i64, turn)) as usize;
    matches!(ord, 1 | 2 | 3 | 4 | 6).then_some(ord)
}

/// Apply `gens` (and rely on inverses being included) breadth-first from the
/// identity to fill a disk of `radius` (centroid distance), capped at `cap`
/// placements. The identity (central tile) is placement 0. A non-discrete
/// generator set just hits `cap`; the caller's verification rejects it.
pub(crate) fn build_orbit<T: IsRing>(
    verts: &[T],
    gens: &[Iso<T>],
    radius: f64,
    cap: usize,
) -> Vec<Iso<T>> {
    use std::collections::{HashSet, VecDeque};
    let mut seen: HashSet<Iso<T>> = HashSet::new();
    let mut placements: Vec<Iso<T>> = Vec::new();
    let mut q: VecDeque<Iso<T>> = VecDeque::new();
    let start = Iso::id();
    seen.insert(start);
    placements.push(start);
    q.push_back(start);
    let r2 = radius * radius;
    while let Some(cur) = q.pop_front() {
        if placements.len() >= cap {
            break;
        }
        for g in gens {
            let nxt = g.after(&cur);
            if seen.contains(&nxt) {
                continue;
            }
            let (cx, cy) = nxt.centroid(verts);
            if cx * cx + cy * cy > r2 {
                continue;
            }
            seen.insert(nxt);
            placements.push(nxt);
            q.push_back(nxt);
        }
    }
    placements
}