proof_engine/topology/
tiling.rs

1// topology/tiling.rs — Fundamental domains, wallpaper groups, and tilings
2
3use glam::Vec2;
4use std::f32::consts::PI;
5
6// ─── Wallpaper Groups ──────────────────────────────────────────────────────
7
8/// All 17 wallpaper groups (2D crystallographic groups).
9#[derive(Clone, Copy, Debug, PartialEq)]
10pub enum WallpaperGroup {
11    P1,
12    P2,
13    PM,
14    PG,
15    CM,
16    P2MM,
17    P2MG,
18    P2GG,
19    C2MM,
20    P4,
21    P4MM,
22    P4GM,
23    P3,
24    P3M1,
25    P31M,
26    P6,
27    P6MM,
28}
29
30/// A tile instance placed in the plane.
31#[derive(Clone, Debug)]
32pub struct TileInstance {
33    pub position: Vec2,
34    pub rotation: f32,
35    pub mirror: bool,
36}
37
38/// A fundamental domain defined by its vertices.
39#[derive(Clone, Debug)]
40pub struct FundamentalDomain {
41    pub vertices: Vec<Vec2>,
42}
43
44impl FundamentalDomain {
45    /// Create a rectangular fundamental domain.
46    pub fn rectangle(width: f32, height: f32) -> Self {
47        Self {
48            vertices: vec![
49                Vec2::ZERO,
50                Vec2::new(width, 0.0),
51                Vec2::new(width, height),
52                Vec2::new(0.0, height),
53            ],
54        }
55    }
56
57    /// Create a rhombus fundamental domain.
58    pub fn rhombus(a: f32, angle: f32) -> Self {
59        let dx = a * angle.cos();
60        let dy = a * angle.sin();
61        Self {
62            vertices: vec![
63                Vec2::ZERO,
64                Vec2::new(a, 0.0),
65                Vec2::new(a + dx, dy),
66                Vec2::new(dx, dy),
67            ],
68        }
69    }
70
71    /// Create an equilateral triangle fundamental domain.
72    pub fn equilateral_triangle(side: f32) -> Self {
73        Self {
74            vertices: vec![
75                Vec2::ZERO,
76                Vec2::new(side, 0.0),
77                Vec2::new(side / 2.0, side * (3.0_f32).sqrt() / 2.0),
78            ],
79        }
80    }
81}
82
83/// Generate a tiling by applying the symmetries of the given wallpaper group
84/// to the fundamental domain, filling the area [-extent, extent] x [-extent, extent].
85pub fn generate_tiling(group: WallpaperGroup, domain: &FundamentalDomain, extent: f32) -> Vec<TileInstance> {
86    let (t1, t2, symmetries) = group_generators(group, domain);
87
88    let mut tiles = Vec::new();
89    let max_n = (extent / t1.length().max(0.01)) as i32 + 2;
90    let max_m = (extent / t2.length().max(0.01)) as i32 + 2;
91
92    for n in -max_n..=max_n {
93        for m in -max_m..=max_m {
94            let base = t1 * n as f32 + t2 * m as f32;
95
96            for sym in &symmetries {
97                let pos = base + sym.offset;
98                if pos.x.abs() <= extent && pos.y.abs() <= extent {
99                    tiles.push(TileInstance {
100                        position: pos,
101                        rotation: sym.rotation,
102                        mirror: sym.mirror,
103                    });
104                }
105            }
106        }
107    }
108    tiles
109}
110
111struct SymOp {
112    offset: Vec2,
113    rotation: f32,
114    mirror: bool,
115}
116
117/// Return translation vectors and symmetry operations for a wallpaper group.
118fn group_generators(group: WallpaperGroup, domain: &FundamentalDomain) -> (Vec2, Vec2, Vec<SymOp>) {
119    // Compute a bounding size from the domain
120    let mut max_x = 0.0_f32;
121    let mut max_y = 0.0_f32;
122    for v in &domain.vertices {
123        max_x = max_x.max(v.x);
124        max_y = max_y.max(v.y);
125    }
126    let w = max_x.max(1.0);
127    let h = max_y.max(1.0);
128
129    match group {
130        WallpaperGroup::P1 => (
131            Vec2::new(w, 0.0),
132            Vec2::new(0.0, h),
133            vec![SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false }],
134        ),
135        WallpaperGroup::P2 => (
136            Vec2::new(w, 0.0),
137            Vec2::new(0.0, h),
138            vec![
139                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
140                SymOp { offset: Vec2::new(w / 2.0, h / 2.0), rotation: PI, mirror: false },
141            ],
142        ),
143        WallpaperGroup::PM => (
144            Vec2::new(w, 0.0),
145            Vec2::new(0.0, h),
146            vec![
147                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
148                SymOp { offset: Vec2::new(0.0, h), rotation: 0.0, mirror: true },
149            ],
150        ),
151        WallpaperGroup::PG => (
152            Vec2::new(w, 0.0),
153            Vec2::new(0.0, h),
154            vec![
155                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
156                SymOp { offset: Vec2::new(w / 2.0, 0.0), rotation: 0.0, mirror: true },
157            ],
158        ),
159        WallpaperGroup::CM => (
160            Vec2::new(w, 0.0),
161            Vec2::new(w / 2.0, h),
162            vec![
163                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
164                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: true },
165            ],
166        ),
167        WallpaperGroup::P2MM => (
168            Vec2::new(w, 0.0),
169            Vec2::new(0.0, h),
170            vec![
171                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
172                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: false },
173                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: true },
174                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: true },
175            ],
176        ),
177        WallpaperGroup::P2MG => (
178            Vec2::new(w, 0.0),
179            Vec2::new(0.0, h),
180            vec![
181                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
182                SymOp { offset: Vec2::new(w / 2.0, 0.0), rotation: PI, mirror: false },
183                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: true },
184                SymOp { offset: Vec2::new(w / 2.0, 0.0), rotation: PI, mirror: true },
185            ],
186        ),
187        WallpaperGroup::P2GG => (
188            Vec2::new(w, 0.0),
189            Vec2::new(0.0, h),
190            vec![
191                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
192                SymOp { offset: Vec2::new(w / 2.0, h / 2.0), rotation: PI, mirror: false },
193                SymOp { offset: Vec2::new(w / 2.0, 0.0), rotation: 0.0, mirror: true },
194                SymOp { offset: Vec2::new(0.0, h / 2.0), rotation: PI, mirror: true },
195            ],
196        ),
197        WallpaperGroup::C2MM => (
198            Vec2::new(w, 0.0),
199            Vec2::new(w / 2.0, h),
200            vec![
201                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
202                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: false },
203                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: true },
204                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: true },
205            ],
206        ),
207        WallpaperGroup::P4 => (
208            Vec2::new(w, 0.0),
209            Vec2::new(0.0, w), // square lattice
210            vec![
211                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
212                SymOp { offset: Vec2::ZERO, rotation: PI / 2.0, mirror: false },
213                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: false },
214                SymOp { offset: Vec2::ZERO, rotation: 3.0 * PI / 2.0, mirror: false },
215            ],
216        ),
217        WallpaperGroup::P4MM => (
218            Vec2::new(w, 0.0),
219            Vec2::new(0.0, w),
220            vec![
221                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
222                SymOp { offset: Vec2::ZERO, rotation: PI / 2.0, mirror: false },
223                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: false },
224                SymOp { offset: Vec2::ZERO, rotation: 3.0 * PI / 2.0, mirror: false },
225                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: true },
226                SymOp { offset: Vec2::ZERO, rotation: PI / 2.0, mirror: true },
227                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: true },
228                SymOp { offset: Vec2::ZERO, rotation: 3.0 * PI / 2.0, mirror: true },
229            ],
230        ),
231        WallpaperGroup::P4GM => (
232            Vec2::new(w, 0.0),
233            Vec2::new(0.0, w),
234            vec![
235                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
236                SymOp { offset: Vec2::new(w / 2.0, w / 2.0), rotation: PI / 2.0, mirror: false },
237                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: false },
238                SymOp { offset: Vec2::new(w / 2.0, w / 2.0), rotation: 3.0 * PI / 2.0, mirror: false },
239                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: true },
240                SymOp { offset: Vec2::new(w / 2.0, w / 2.0), rotation: PI / 2.0, mirror: true },
241                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: true },
242                SymOp { offset: Vec2::new(w / 2.0, w / 2.0), rotation: 3.0 * PI / 2.0, mirror: true },
243            ],
244        ),
245        WallpaperGroup::P3 => {
246            let t1 = Vec2::new(w, 0.0);
247            let t2 = Vec2::new(w / 2.0, w * (3.0_f32).sqrt() / 2.0);
248            (t1, t2, vec![
249                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
250                SymOp { offset: Vec2::ZERO, rotation: 2.0 * PI / 3.0, mirror: false },
251                SymOp { offset: Vec2::ZERO, rotation: 4.0 * PI / 3.0, mirror: false },
252            ])
253        }
254        WallpaperGroup::P3M1 => {
255            let t1 = Vec2::new(w, 0.0);
256            let t2 = Vec2::new(w / 2.0, w * (3.0_f32).sqrt() / 2.0);
257            (t1, t2, vec![
258                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
259                SymOp { offset: Vec2::ZERO, rotation: 2.0 * PI / 3.0, mirror: false },
260                SymOp { offset: Vec2::ZERO, rotation: 4.0 * PI / 3.0, mirror: false },
261                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: true },
262                SymOp { offset: Vec2::ZERO, rotation: 2.0 * PI / 3.0, mirror: true },
263                SymOp { offset: Vec2::ZERO, rotation: 4.0 * PI / 3.0, mirror: true },
264            ])
265        }
266        WallpaperGroup::P31M => {
267            let t1 = Vec2::new(w, 0.0);
268            let t2 = Vec2::new(w / 2.0, w * (3.0_f32).sqrt() / 2.0);
269            (t1, t2, vec![
270                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
271                SymOp { offset: Vec2::ZERO, rotation: 2.0 * PI / 3.0, mirror: false },
272                SymOp { offset: Vec2::ZERO, rotation: 4.0 * PI / 3.0, mirror: false },
273                SymOp { offset: Vec2::ZERO, rotation: PI / 3.0, mirror: true },
274                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: true },
275                SymOp { offset: Vec2::ZERO, rotation: 5.0 * PI / 3.0, mirror: true },
276            ])
277        }
278        WallpaperGroup::P6 => {
279            let t1 = Vec2::new(w, 0.0);
280            let t2 = Vec2::new(w / 2.0, w * (3.0_f32).sqrt() / 2.0);
281            (t1, t2, vec![
282                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
283                SymOp { offset: Vec2::ZERO, rotation: PI / 3.0, mirror: false },
284                SymOp { offset: Vec2::ZERO, rotation: 2.0 * PI / 3.0, mirror: false },
285                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: false },
286                SymOp { offset: Vec2::ZERO, rotation: 4.0 * PI / 3.0, mirror: false },
287                SymOp { offset: Vec2::ZERO, rotation: 5.0 * PI / 3.0, mirror: false },
288            ])
289        }
290        WallpaperGroup::P6MM => {
291            let t1 = Vec2::new(w, 0.0);
292            let t2 = Vec2::new(w / 2.0, w * (3.0_f32).sqrt() / 2.0);
293            (t1, t2, vec![
294                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: false },
295                SymOp { offset: Vec2::ZERO, rotation: PI / 3.0, mirror: false },
296                SymOp { offset: Vec2::ZERO, rotation: 2.0 * PI / 3.0, mirror: false },
297                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: false },
298                SymOp { offset: Vec2::ZERO, rotation: 4.0 * PI / 3.0, mirror: false },
299                SymOp { offset: Vec2::ZERO, rotation: 5.0 * PI / 3.0, mirror: false },
300                SymOp { offset: Vec2::ZERO, rotation: 0.0, mirror: true },
301                SymOp { offset: Vec2::ZERO, rotation: PI / 3.0, mirror: true },
302                SymOp { offset: Vec2::ZERO, rotation: 2.0 * PI / 3.0, mirror: true },
303                SymOp { offset: Vec2::ZERO, rotation: PI, mirror: true },
304                SymOp { offset: Vec2::ZERO, rotation: 4.0 * PI / 3.0, mirror: true },
305                SymOp { offset: Vec2::ZERO, rotation: 5.0 * PI / 3.0, mirror: true },
306            ])
307        }
308    }
309}
310
311// ─── Penrose Tiling ────────────────────────────────────────────────────────
312
313/// Penrose tile types: the two rhombus shapes in P3 Penrose tiling.
314#[derive(Clone, Copy, Debug, PartialEq)]
315pub enum PenroseType {
316    /// Thin rhombus (36/144 degree angles)
317    Thin,
318    /// Thick rhombus (72/108 degree angles)
319    Thick,
320}
321
322/// A single Penrose tile.
323#[derive(Clone, Debug)]
324pub struct PenroseTile {
325    pub vertices: Vec<Vec2>,
326    pub tile_type: PenroseType,
327}
328
329/// Generate a Penrose tiling using the Robinson triangle decomposition.
330/// `depth` controls the number of subdivision iterations.
331pub fn generate_penrose(depth: usize) -> Vec<PenroseTile> {
332    let golden = (1.0 + 5.0_f32.sqrt()) / 2.0;
333
334    // Start with a wheel of 10 "half-kite" triangles
335    let mut triangles: Vec<(bool, Vec2, Vec2, Vec2)> = Vec::new(); // (is_type_a, A, B, C)
336
337    for i in 0..10 {
338        let angle1 = 2.0 * PI * i as f32 / 10.0;
339        let angle2 = 2.0 * PI * (i + 1) as f32 / 10.0;
340
341        let b = Vec2::new(angle1.cos(), angle1.sin());
342        let c = Vec2::new(angle2.cos(), angle2.sin());
343
344        if i % 2 == 0 {
345            triangles.push((true, Vec2::ZERO, b, c));
346        } else {
347            triangles.push((true, Vec2::ZERO, c, b));
348        }
349    }
350
351    // Subdivide
352    for _ in 0..depth {
353        let mut new_triangles = Vec::new();
354        for &(is_a, a, b, c) in &triangles {
355            if is_a {
356                // Subdivide acute triangle
357                let p = a + (b - a) / golden;
358                new_triangles.push((true, c, p, b));
359                new_triangles.push((false, p, c, a));
360            } else {
361                // Subdivide obtuse triangle
362                let q = b + (a - b) / golden;
363                let r = b + (c - b) / golden;
364                new_triangles.push((false, r, c, a));
365                new_triangles.push((false, q, r, b));
366                new_triangles.push((true, r, q, a));
367            }
368        }
369        triangles = new_triangles;
370    }
371
372    // Convert pairs of triangles into rhombus tiles
373    // For simplicity, output each triangle pair as a tile
374    let mut tiles = Vec::new();
375    let mut used = vec![false; triangles.len()];
376
377    for i in 0..triangles.len() {
378        if used[i] {
379            continue;
380        }
381
382        let (is_a_i, a_i, b_i, c_i) = triangles[i];
383
384        // Try to find a matching triangle to form a rhombus
385        let mut found = false;
386        for j in (i + 1)..triangles.len() {
387            if used[j] {
388                continue;
389            }
390            let (is_a_j, a_j, b_j, c_j) = triangles[j];
391            if is_a_i != is_a_j {
392                continue;
393            }
394
395            // Check if they share an edge (B-C)
396            let share = (b_i - b_j).length() < 0.01 && (c_i - c_j).length() < 0.01
397                || (b_i - c_j).length() < 0.01 && (c_i - b_j).length() < 0.01;
398
399            if share {
400                let tile_type = if is_a_i { PenroseType::Thin } else { PenroseType::Thick };
401                tiles.push(PenroseTile {
402                    vertices: vec![a_i, b_i, a_j, c_i],
403                    tile_type,
404                });
405                used[i] = true;
406                used[j] = true;
407                found = true;
408                break;
409            }
410        }
411
412        if !found {
413            // Unpaired triangle — output as a degenerate tile
414            let tile_type = if is_a_i { PenroseType::Thin } else { PenroseType::Thick };
415            tiles.push(PenroseTile {
416                vertices: vec![a_i, b_i, c_i],
417                tile_type,
418            });
419            used[i] = true;
420        }
421    }
422
423    tiles
424}
425
426// ─── Tests ─────────────────────────────────────────────────────────────────
427
428#[cfg(test)]
429mod tests {
430    use super::*;
431
432    #[test]
433    fn test_p1_tiling() {
434        let domain = FundamentalDomain::rectangle(1.0, 1.0);
435        let tiles = generate_tiling(WallpaperGroup::P1, &domain, 5.0);
436        assert!(!tiles.is_empty());
437        // P1 has one copy per unit cell
438        for tile in &tiles {
439            assert!(!tile.mirror);
440            assert!((tile.rotation).abs() < 1e-6);
441        }
442    }
443
444    #[test]
445    fn test_p4_tiling() {
446        let domain = FundamentalDomain::rectangle(1.0, 1.0);
447        let tiles = generate_tiling(WallpaperGroup::P4, &domain, 3.0);
448        assert!(!tiles.is_empty());
449        // P4 has 4 rotations per unit cell
450    }
451
452    #[test]
453    fn test_p6mm_tiling() {
454        let domain = FundamentalDomain::equilateral_triangle(1.0);
455        let tiles = generate_tiling(WallpaperGroup::P6MM, &domain, 3.0);
456        assert!(!tiles.is_empty());
457        // P6MM has 12 symmetry operations
458    }
459
460    #[test]
461    fn test_all_17_groups_produce_tiles() {
462        let domain = FundamentalDomain::rectangle(1.0, 1.0);
463        let groups = [
464            WallpaperGroup::P1, WallpaperGroup::P2, WallpaperGroup::PM,
465            WallpaperGroup::PG, WallpaperGroup::CM, WallpaperGroup::P2MM,
466            WallpaperGroup::P2MG, WallpaperGroup::P2GG, WallpaperGroup::C2MM,
467            WallpaperGroup::P4, WallpaperGroup::P4MM, WallpaperGroup::P4GM,
468            WallpaperGroup::P3, WallpaperGroup::P3M1, WallpaperGroup::P31M,
469            WallpaperGroup::P6, WallpaperGroup::P6MM,
470        ];
471        for group in groups {
472            let tiles = generate_tiling(group, &domain, 2.0);
473            assert!(!tiles.is_empty(), "Group {:?} produced no tiles", group);
474        }
475    }
476
477    #[test]
478    fn test_fundamental_domain_rectangle() {
479        let d = FundamentalDomain::rectangle(2.0, 3.0);
480        assert_eq!(d.vertices.len(), 4);
481    }
482
483    #[test]
484    fn test_fundamental_domain_rhombus() {
485        let d = FundamentalDomain::rhombus(1.0, PI / 3.0);
486        assert_eq!(d.vertices.len(), 4);
487    }
488
489    #[test]
490    fn test_fundamental_domain_triangle() {
491        let d = FundamentalDomain::equilateral_triangle(1.0);
492        assert_eq!(d.vertices.len(), 3);
493    }
494
495    #[test]
496    fn test_penrose_tiling_depth_0() {
497        let tiles = generate_penrose(0);
498        assert!(!tiles.is_empty());
499    }
500
501    #[test]
502    fn test_penrose_tiling_depth_3() {
503        let tiles = generate_penrose(3);
504        assert!(tiles.len() > 10, "Depth-3 Penrose should have many tiles, got {}", tiles.len());
505    }
506
507    #[test]
508    fn test_penrose_has_both_types() {
509        let tiles = generate_penrose(3);
510        let has_thin = tiles.iter().any(|t| t.tile_type == PenroseType::Thin);
511        let has_thick = tiles.iter().any(|t| t.tile_type == PenroseType::Thick);
512        assert!(has_thin, "Should have thin tiles");
513        assert!(has_thick, "Should have thick tiles");
514    }
515
516    #[test]
517    fn test_penrose_tile_vertices() {
518        let tiles = generate_penrose(2);
519        for tile in &tiles {
520            assert!(tile.vertices.len() >= 3);
521            for v in &tile.vertices {
522                // All vertices should be within a reasonable range of the origin
523                assert!(v.length() < 5.0, "Vertex too far: {:?}", v);
524            }
525        }
526    }
527}
proof_engine/topology/tiling.rs

proof_engine/topology/
tiling.rs
