tilezz 0.0.1

Utilities to work with perfect-precision polygonal tiles built on top of complex 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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

use super::gaussint::GaussInt;
use super::zzbase::ZZNum;
use num_traits::One;
use std::collections::HashMap;

// Misc utils
// ----------

/// Get reverse complement of an angle sequence,
/// i.e. with reversed order and sign.
pub fn revcomp(angles: &[i8]) -> Vec<i8> {
    angles.iter().rev().map(|a| -a).collect()
}

/// Normalize an angle to (-half-turn, half-turn). This is
/// used to have a unique symbolic snake representation.
pub fn normalize_angle<T: ZZNum>(angle: i8) -> i8 {
    let a = angle % T::turn();
    if a.abs() <= T::hturn() {
        a
    } else {
        -(a.signum() * T::turn() - a)
    }
}

// Unit square lattice utils
// -------------------------

/// Return coordinates of closest unit square lattice cell
/// that a complex integer falls in. The cells are centered
/// at points that are pairs of two integers in the complex plane.
pub fn cell_of<T: ZZNum>(zz: T) -> GaussInt<i64> {
    let c = zz.complex();
    GaussInt {
        real: c.re.round() as i64,
        imag: c.im.round() as i64,
    }
}

/// Given a complex integer point, return the 5 unit square lattice cells
/// that make up the neighborhood of the cell of the point.
pub fn cell_neighborhood_of<T: ZZNum>(zz: T) -> Vec<GaussInt<i64>> {
    let c = cell_of(zz);
    let r = GaussInt::new(c.real + 1, c.imag);
    let l = GaussInt::new(c.real - 1, c.imag);
    let u = GaussInt::new(c.real, c.imag + 1);
    let d = GaussInt::new(c.real, c.imag - 1);
    vec![l, d, c, u, r] // sorted by first x, then y
}

/// Given endpoints of a unit length line segment,
/// returns the 5 or 8 distinct unit square lattice cells that:
/// 1. the line segment is guaranteed to be fully contained inside, and
/// 2. all intersecting unit length segments also have at least one point in it.
pub fn seg_neighborhood_of<T: ZZNum>(p1: T, p2: T) -> Vec<GaussInt<i64>> {
    let mut result = cell_neighborhood_of(p1);
    result.extend(cell_neighborhood_of(p2));
    result.sort();
    result.dedup();
    result
}

/// Returns indices of all points in the given unit square lattice
/// that are located inside one of the given cells.
///
/// Note that this does neither sort not deduplicate points.
pub fn indices_from_cells(
    lattice: &HashMap<GaussInt<i64>, Vec<usize>>,
    cells: &[GaussInt<i64>],
) -> Vec<usize> {
    let mut pt_indices: Vec<usize> = Vec::new();
    for cell in cells {
        lattice.get(&cell).and_then(|pts| {
            pt_indices.extend(pts);
            None::<()>
        });
    }
    pt_indices
}

// 2D geometry utils
// -----------------

fn is_ccw<T: ZZNum>(a: T, b: T, c: T) -> bool {
    (b - a).wedge(&(c - a)).re_signum().is_one()
}

/// Return whether line segments AB and CD intersect.
/// Note that touching in only endpoints does not count as intersection.
/// Based on: https://stackoverflow.com/a/9997374/432908
pub fn intersect<T: ZZNum>(&(a, b): &(T, T), &(c, d): &(T, T)) -> bool {
    let l_ab = a.line_through(&b);
    if c.is_colinear(&l_ab) && d.is_colinear(&l_ab) {
        c.is_between(&a, &b) || d.is_between(&a, &b)
    } else {
        if a == c || a == d || b == c || b == d {
            false // ignore touching endpoints in non-colinear case
        } else {
            is_ccw(a, c, d) != is_ccw(b, c, d) && is_ccw(a, b, c) != is_ccw(a, b, d)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::zz::ZZ12;
    use crate::zzbase::ZZBase;
    use num_traits::{One, Zero};

    #[test]
    fn test_revcomp() {
        assert_eq!(revcomp(vec![].as_slice()), vec![]);
        assert_eq!(revcomp(vec![6].as_slice()), vec![-6]);
        let v = vec![1, 3, -2, 4];
        assert_eq!(revcomp(v.as_slice()), vec![-4, 2, -3, -1]);
        assert_eq!(revcomp(revcomp(v.as_slice()).as_slice()).as_slice(), v);
    }

    #[test]
    fn test_normalize_angles() {
        assert_eq!(normalize_angle::<ZZ12>(0), 0);
        assert_eq!(normalize_angle::<ZZ12>(1), 1);
        assert_eq!(normalize_angle::<ZZ12>(-1), -1);
        assert_eq!(normalize_angle::<ZZ12>(5), 5);
        assert_eq!(normalize_angle::<ZZ12>(-5), -5);
        assert_eq!(normalize_angle::<ZZ12>(6), 6);
        assert_eq!(normalize_angle::<ZZ12>(-6), -6);
        assert_eq!(normalize_angle::<ZZ12>(7), -5);
        assert_eq!(normalize_angle::<ZZ12>(-7), 5);
        assert_eq!(normalize_angle::<ZZ12>(11), -1);
        assert_eq!(normalize_angle::<ZZ12>(-11), 1);
        assert_eq!(normalize_angle::<ZZ12>(12), 0);
        assert_eq!(normalize_angle::<ZZ12>(-12), 0);
        assert_eq!(normalize_angle::<ZZ12>(13), 1);
        assert_eq!(normalize_angle::<ZZ12>(-13), -1);
    }

    #[test]
    fn test_indices_from_cells() {
        let grid: HashMap<GaussInt<i64>, Vec<usize>> = HashMap::from([
            (GaussInt::new(0, 0), vec![0, 1]),
            (GaussInt::new(1, 0), vec![2, 0]),
        ]);

        // sanity-check
        assert_eq!(indices_from_cells(&grid, &[GaussInt::new(0, 0)]), &[0, 1]);
        assert_eq!(indices_from_cells(&grid, &[GaussInt::new(1, 0)]), &[2, 0]);
        assert_eq!(indices_from_cells(&grid, &[GaussInt::new(2, 0)]), &[]);

        // combined results are simply concatenated
        assert_eq!(
            indices_from_cells(
                &grid,
                &[
                    GaussInt::new(2, 0),
                    GaussInt::new(1, 0),
                    GaussInt::new(0, 0)
                ]
            ),
            &[2, 0, 0, 1]
        );
    }

    #[test]
    fn test_intersect() {
        let a: ZZ12 = ZZ12::zero();
        let b: ZZ12 = ZZ12::one();
        let c: ZZ12 = ZZ12::from(2);
        let d: ZZ12 = ZZ12::from(3);
        let e: ZZ12 = ZZ12::one_i();
        let f: ZZ12 = b + e;

        // colinear cases:
        // ----
        assert!(!intersect(&(a, b), &(c, d))); // no touch
        assert!(!intersect(&(d, c), &(a, b))); // same, permutated
        assert!(!intersect(&(a, b), &(b, c))); // touch in an endpoint
        assert!(intersect(&(a, c), &(b, d))); // overlap
        assert!(intersect(&(a, d), &(b, c))); // overlap (subsuming)

        // non-colinear cases:
        // ----
        // parallel
        assert!(!intersect(&(a, b), &(e, f)));
        assert!(!intersect(&(a, e), &(b, f)));

        // no touch
        assert!(!intersect(&(a, e), &(b, c))); // perp
        assert!(!intersect(&(a, f), &(b, c))); // non-perp

        // touch in start/end-points
        assert!(!intersect(&(a, e), &(a, b))); // perp
        assert!(!intersect(&(a, f), &(a, b))); // non-perp
        assert!(!intersect(&(a, e), &(e, e - b))); // non-perp

        // endpoint of one segment intersects a non-endpoint of other seg
        assert!(intersect(&(b, f), &(a, c))); // perp
        assert!(intersect(&(b, e), &(a, c))); // non-perp

        // proper intersection of open segments
        assert!(intersect(&(a, f), &(b, e))); // perp
        assert!(intersect(&(a, f), &(c, e))); // non-perp
        assert!(intersect(&(a, f), &(d, e))); // non-perp
    }
}