layer_proc_gen/
vec2.rs

1//! Various position related data structures for 2d integer position handling.
2
3use derive_more::derive::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};
4use rand::{
5    distr::{
6        StandardUniform,
7        uniform::{SampleRange, SampleUniform},
8    },
9    prelude::*,
10};
11use std::{
12    cmp::Ordering,
13    num::NonZeroU16,
14    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
15};
16
17/// A 2d point where you can choose the type and thus precision of the x and y indices.
18/// By default uses [i64] which is the world coordinate type.
19#[derive(
20    Copy,
21    Clone,
22    PartialEq,
23    Eq,
24    PartialOrd,
25    Ord,
26    AddAssign,
27    Add,
28    Mul,
29    MulAssign,
30    Sub,
31    SubAssign,
32    Div,
33    DivAssign,
34    Default,
35)]
36#[mul(forward)]
37#[div(forward)]
38#[mul_assign(forward)]
39#[div_assign(forward)]
40pub struct Point2d<T = i64> {
41    /// `x` position
42    pub x: T,
43    /// `y` position
44    pub y: T,
45}
46
47/// A line segment with a direction.
48#[derive(PartialEq, Debug, Copy, Clone)]
49pub struct Line<T = i64> {
50    /// The start of the line segment.
51    pub start: Point2d<T>,
52    /// The end of the line segment.
53    pub end: Point2d<T>,
54}
55
56impl Line {
57    /// Returns a point where two line segments intersect (if any).
58    // impl from https://stackoverflow.com/a/14795484
59    pub fn get_intersection(self, other: Self) -> Option<Point2d> {
60        let s10 = self.end - self.start;
61        let s32 = other.end - other.start;
62
63        let denom = s10.x * s32.y - s32.x * s10.y;
64        if denom == 0 {
65            return None; // Collinear
66        }
67        let denom_positive = denom > 0;
68
69        let s02 = self.start - other.start;
70        let s_numer = s10.x * s02.y - s10.y * s02.x;
71        if (s_numer < 0) == denom_positive {
72            return None; // No collision
73        }
74        let t_numer = s32.x * s02.y - s32.y * s02.x;
75        if (t_numer < 0) == denom_positive {
76            return None; // No collision
77        }
78        if (s_numer > denom) == denom_positive || (t_numer > denom) == denom_positive {
79            return None; // No collision
80        }
81        // Collision detected
82        let t = t_numer / denom;
83
84        Some(self.start + s10 * t)
85    }
86
87    /// Create bounds where this line is the diagonal of.
88    pub fn bounds(&self) -> Bounds {
89        Bounds {
90            min: self.start,
91            max: self.end,
92        }
93    }
94
95    /// Shorten the line to make its manhattan length the given one.
96    pub fn with_manhattan_length(self, len: i64) -> Self {
97        assert!(len > 0);
98        let dir = self.end - self.start;
99        let old_len = dir.x.abs() + dir.y.abs();
100        let new_dir = dir * len / old_len;
101        Self {
102            start: self.start,
103            end: self.start + new_dir,
104        }
105    }
106
107    /// Swap the end and the start.
108    pub fn flip(self) -> Self {
109        Self {
110            start: self.end,
111            end: self.start,
112        }
113    }
114
115    /// Compute the square of the length.
116    pub fn len_squared(&self) -> i64 {
117        (self.end - self.start).len_squared()
118    }
119}
120
121impl<T: Num> Line<T> {
122    /// Iterate over all pixes that are touched by this line.
123    pub fn iter_all_touched_pixels(mut self, mut pnt: impl FnMut(Point2d<T>)) {
124        // https://makemeengr.com/precise-subpixel-line-drawing-algorithm-rasterization-algorithm/
125        let mut k = Point2d::splat(T::ZERO);
126        self.end -= self.start;
127
128        // Pick x direction and step magnitude
129        match self.end.x.cmp(&T::ZERO) {
130            Ordering::Greater => k.x = T::ONE,
131            Ordering::Equal => {}
132            Ordering::Less => {
133                k.x = -T::ONE;
134                self.end.x = -self.end.x;
135            }
136        }
137        self.end.x += T::ONE;
138
139        // Pick y direction and step magnitude
140        match self.end.y.cmp(&T::ZERO) {
141            Ordering::Less => k.y = T::ONE,
142            Ordering::Equal => {}
143            Ordering::Greater => {
144                k.y = -T::ONE;
145                self.end.y = -self.end.y;
146            }
147        }
148        self.end.y += T::ONE;
149
150        // Move in the dimension that steps by more than 1 per step
151        let flip = self.end.x >= self.end.y;
152        if flip {
153            self.end = self.end.flip();
154            self.start = self.start.flip();
155            k = k.flip();
156        }
157        let mut pnt = |p: Point2d<T>| if flip { pnt(p.flip()) } else { pnt(p) };
158
159        let mut c = self.end.y;
160        for i in T::iter_range(T::ZERO..self.end.y) {
161            pnt(self.start); // This is the normal pixel. The two below are subpixels
162            c -= self.end.x;
163            if c <= T::ZERO {
164                if i != self.end.y - T::ONE {
165                    pnt(self.start + Point2d::new(T::ZERO, k.y));
166                }
167                c += self.end.y;
168                self.start.x += k.x;
169                if i != self.end.y - T::ONE {
170                    pnt(self.start);
171                }
172            }
173            self.start.y += k.y
174        }
175    }
176}
177
178impl<T: std::fmt::Debug> std::fmt::Debug for Point2d<T> {
179    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
180        (&self.x, &self.y).fmt(f)
181    }
182}
183
184impl<T> Distribution<Point2d<T>> for StandardUniform
185where
186    StandardUniform: Distribution<T>,
187{
188    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Point2d<T> {
189        Point2d {
190            x: self.sample(rng),
191            y: self.sample(rng),
192        }
193    }
194}
195
196impl<T: Copy> Point2d<T> {
197    /// Set `x` and `y` to the same value
198    pub const fn splat(arg: T) -> Self {
199        Self::new(arg, arg)
200    }
201
202    /// Basic constructor for when struct constructors are too inconvenient
203    pub const fn new(x: T, y: T) -> Self {
204        Self { x, y }
205    }
206
207    /// Apply a closure to both `x` and `y`
208    pub fn map<U>(&self, f: impl Fn(T) -> U) -> Point2d<U> {
209        Point2d {
210            x: f(self.x),
211            y: f(self.y),
212        }
213    }
214
215    /// Connect a line segment from this point to the argument.
216    pub fn to(self, other: Self) -> Line<T> {
217        Line {
218            start: self,
219            end: other,
220        }
221    }
222
223    fn flip(self) -> Point2d<T> {
224        Point2d {
225            x: self.y,
226            y: self.x,
227        }
228    }
229}
230
231impl<T: Neg<Output = T>> Point2d<T> {
232    /// Return the perpendicular (right facing) vector of the same length.
233    pub fn perp(self) -> Self {
234        Self {
235            x: -self.y,
236            y: self.x,
237        }
238    }
239}
240
241/// Helper trait for computing absolute values of generic types.
242pub trait Abs {
243    /// Compute the absolute value of this type.
244    /// No-op if the value is alread positive.
245    fn abs(self) -> Self;
246}
247
248impl Abs for i64 {
249    fn abs(self) -> Self {
250        i64::abs(self)
251    }
252}
253
254impl<T: Copy + Sub<Output = T> + Mul<Output = T> + Add<Output = T> + Abs> Point2d<T> {
255    /// The square of the distance between two points
256    pub fn dist_squared(self, center: Point2d<T>) -> T {
257        (self - center).len_squared()
258    }
259
260    /// The square of the distance between the origin (`0, 0`) and this point.
261    pub fn len_squared(self) -> T {
262        let Self { x, y } = self;
263        x * x + y * y
264    }
265
266    /// The manhattan distance between two points.
267    pub fn manhattan_dist(self, city: Point2d<T>) -> T {
268        let diff = city - self;
269        diff.manhattan_len()
270    }
271
272    /// The manhattan distance to the origin.
273    pub fn manhattan_len(&self) -> T {
274        self.x.abs() + self.y.abs()
275    }
276}
277
278impl From<Point2d<NonZeroU16>> for Point2d {
279    fn from(value: Point2d<NonZeroU16>) -> Self {
280        Self {
281            x: value.x.get().into(),
282            y: value.y.get().into(),
283        }
284    }
285}
286
287impl Point2d<i64> {
288    /// Subtract two points element wise.
289    pub const fn sub(mut self, rhs: Point2d) -> Point2d {
290        self.x -= rhs.x;
291        self.y -= rhs.y;
292        self
293    }
294
295    /// Multiply two points element wise.
296    pub const fn mul(mut self, rhs: Point2d) -> Point2d {
297        self.x *= rhs.x;
298        self.y *= rhs.y;
299        self
300    }
301
302    /// Get the bytes of this point in native byte order.
303    pub fn to_ne_bytes(&self) -> [u8; 16] {
304        let mut array = [0; 16];
305        for (dest, src) in array
306            .iter_mut()
307            .zip(self.x.to_ne_bytes().into_iter().chain(self.y.to_ne_bytes()))
308        {
309            *dest = src;
310        }
311        array
312    }
313}
314
315impl<T: DivAssign + Copy> Div<T> for Point2d<T> {
316    type Output = Self;
317    fn div(mut self, rhs: T) -> Self::Output {
318        self /= rhs;
319        self
320    }
321}
322
323impl<T: DivAssign + Copy> DivAssign<T> for Point2d<T> {
324    fn div_assign(&mut self, rhs: T) {
325        self.x /= rhs;
326        self.y /= rhs;
327    }
328}
329
330impl<T: MulAssign + Copy> Mul<T> for Point2d<T> {
331    type Output = Self;
332    fn mul(mut self, rhs: T) -> Self::Output {
333        self *= rhs;
334        self
335    }
336}
337
338impl<T: MulAssign + Copy> MulAssign<T> for Point2d<T> {
339    fn mul_assign(&mut self, rhs: T) {
340        self.x *= rhs;
341        self.y *= rhs;
342    }
343}
344
345#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
346/// A rectangle that includes the minimum and maximum values
347pub struct Bounds<T = i64> {
348    /// The corner closest to the origin.
349    pub min: Point2d<T>,
350    /// The corner furthest away from the origin.
351    pub max: Point2d<T>,
352}
353
354impl<T: std::fmt::Debug> std::fmt::Debug for Bounds<T> {
355    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
356        write!(f, "{:?}..={:?}", self.min, self.max)
357    }
358}
359
360impl<T: Copy + PartialEq + PartialOrd + SampleUniform> Bounds<T> {
361    /// Generate a point within the bounds.
362    pub fn sample<R: RngCore + ?Sized>(self, rng: &mut R) -> Point2d<T> {
363        Point2d {
364            x: (self.min.x..self.max.x).sample_single(rng).unwrap(),
365            y: (self.min.y..self.max.y).sample_single(rng).unwrap(),
366        }
367    }
368
369    /// Apply a closure to both `min` and `max`
370    pub fn map<U>(&self, f: impl Fn(Point2d<T>) -> Point2d<U>) -> Bounds<U> {
371        Bounds {
372            min: f(self.min),
373            max: f(self.max),
374        }
375    }
376}
377
378impl<T: Copy> Bounds<T> {
379    /// Bounds at a single point with zero width and height.
380    pub fn point(point: Point2d<T>) -> Self {
381        Self {
382            min: point,
383            max: point,
384        }
385    }
386}
387
388impl<T: PartialOrd + Num + Copy + AddAssign> Bounds<T> {
389    /// Iterate over all integer points within these bounds.
390    pub fn iter(self) -> impl Iterator<Item = Point2d<T>> {
391        let mut current = self.min;
392        std::iter::from_fn(move || {
393            if current.y > self.max.y {
394                None
395            } else {
396                let item = current;
397                current.x += T::ONE;
398                if current.x > self.max.x {
399                    current.x = self.min.x;
400                    current.y += T::ONE;
401                }
402                Some(item)
403            }
404        })
405    }
406}
407
408impl<T: Copy + Num + Add<Output = T> + Sub<Output = T> + DivAssign<T>> Bounds<T> {
409    /// The middle point of these bounds.
410    pub fn center(&self) -> Point2d<T> {
411        (self.max - self.min) / T::TWO + self.min
412    }
413}
414
415impl<T: Copy + Add<Output = T> + Sub<Output = T>> Bounds<T> {
416    /// Add padding on all sides.
417    pub fn pad(&self, padding: Point2d<T>) -> Self {
418        Self {
419            min: self.min - padding,
420            max: self.max + padding,
421        }
422    }
423}
424
425#[cfg(test)]
426#[test]
427fn iter() {
428    let grid = Bounds {
429        min: Point2d::new(10, 42),
430        max: Point2d::new(12, 43),
431    };
432    let mut iter = grid.iter();
433    assert_eq!(iter.next(), Some(grid.min));
434    assert_eq!(iter.next(), Some(Point2d::new(11, 42)));
435    assert_eq!(iter.next(), Some(Point2d::new(12, 42)));
436    assert_eq!(iter.next(), Some(Point2d::new(10, 43)));
437    assert_eq!(iter.next(), Some(Point2d::new(11, 43)));
438    assert_eq!(iter.next(), Some(Point2d::new(12, 43)));
439    assert_eq!(iter.next(), None);
440    assert_eq!(iter.next(), None);
441}
442
443#[cfg(test)]
444#[test]
445fn iter_point() {
446    let grid = Bounds::point(Point2d::new(10, 42));
447    let mut iter = grid.iter();
448    assert_eq!(iter.next(), Some(grid.min));
449    assert_eq!(iter.next(), None);
450    assert_eq!(iter.next(), None);
451}
452
453impl<T: DivAssign + Copy> Div<Point2d<T>> for Bounds<T> {
454    type Output = Self;
455    fn div(mut self, rhs: Point2d<T>) -> Self::Output {
456        self.min /= rhs;
457        self.max /= rhs;
458        self
459    }
460}
461
462/// A helper trait for specifying generic numeric types.
463pub trait Num:
464    Sized
465    + Copy
466    + AddAssign
467    + SubAssign
468    + Ord
469    + Sub<Output = Self>
470    + Neg<Output = Self>
471    + Eq
472    + Add<Output = Self>
473{
474    /// The neutral value for addition and subtraction.
475    const ZERO: Self;
476    /// The neutral value for multiplication and division.
477    const ONE: Self;
478    /// For when you can't use `+` in const contexts, but need a `2`
479    const TWO: Self;
480    /// Iterate over a range. Workaround to [std::ops::Range]'s [Iterator] impl
481    /// not being implementable for custom types.
482    fn iter_range(range: std::ops::Range<Self>) -> impl Iterator<Item = Self>;
483    /// Convert the value to a [u64]. Used for seeding random number generators
484    /// from coordinates.
485    fn as_u64(self) -> u64;
486}
487
488impl Num for i64 {
489    const ZERO: i64 = 0;
490    const ONE: i64 = 1;
491    const TWO: i64 = 2;
492
493    fn iter_range(range: std::ops::Range<Self>) -> impl Iterator<Item = Self> {
494        range
495    }
496
497    fn as_u64(self) -> u64 {
498        self as u64
499    }
500}
layer_proc_gen/vec2.rs

layer_proc_gen/
vec2.rs
