acacia 0.2.0

A spatial partitioning and tree library.
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

use num_traits::{PrimInt, Float, NumCast};
#[cfg(any(test, feature = "arbitrary"))]
use quickcheck::{Arbitrary, Gen};
use nalgebra::{Vector2, Scalar};
use partition::{Partition, Subdivide};
#[cfg(any(test, feature = "arbitrary"))]
use rand::Rng;


/// A partition of the unit quad [0, 1) × [0, 1)
#[derive(Copy, Clone, Debug, PartialEq, Hash, Eq)]
pub struct UnitQuad {
    scale: u8,
    offset: (u32, u32),
}

impl UnitQuad {
    /// Create a new `UnitQuad`
    ///
    /// This asserts that the offset is valid given the scale level.
    pub fn new(scale: u8, offset: (u32, u32)) -> UnitQuad {
        assert!(scale < 32); // Otherwise exponentiation will overflow
        let max_offset = 2.pow(scale as u32);
        assert!(offset.0 < max_offset && offset.1 < max_offset);
        UnitQuad { scale: scale, offset: offset }
    }

    /// Integer scale
    pub fn scale(&self) -> u8 { self.scale }

    /// Integer offset
    pub fn offset(&self) -> (u32, u32) { self.offset }

    /// Get coordinate within the partition from (u, v) coordinates
    pub fn coordinate<T: Scalar + NumCast + Float>(&self, coord: (T, T)) -> Vector2<T> {
        let (u, v) = coord;
        let width: T = self.width();
        Vector2::new(
            width * (<T as NumCast>::from(self.offset.0).unwrap() + u),
            width * (<T as NumCast>::from(self.offset.1).unwrap() + v),
        )
    }

    /// Center of the partitioned region
    pub fn center<T: Scalar + NumCast + Float>(&self) -> Vector2<T> {
        let half = NumCast::from(0.5).unwrap();
        self.coordinate((half, half))
    }

    /// Width of the partitioned region
    pub fn width<T: Scalar + NumCast + Float>(&self) -> T {
        Float::powi(<T as NumCast>::from(0.5).unwrap(), self.scale as i32)
    }
}

impl Subdivide for UnitQuad {
    fn subdivide(&self) -> Vec<UnitQuad> {
        [(0, 0), (0, 1), (1, 0), (1, 1)]
            .iter()
            .map(|&(di, dj)| {
                let (i, j) = self.offset;
                UnitQuad::new(self.scale + 1, (i * 2 + di, j * 2 + dj))
            })
            .collect()
    }
}

impl<T: Scalar + NumCast + Float> Partition<Vector2<T>> for UnitQuad
{
    fn contains(&self, elem: &Vector2<T>) -> bool {
        let width: T = self.width();
        let offset = Vector2::new(
            width * NumCast::from(self.offset.0).unwrap(),
            width * NumCast::from(self.offset.1).unwrap(),
        );
        (offset.x < elem.x) && (elem.x < offset.x + width) &&
        (offset.y < elem.y) && (elem.y < offset.y + width)
    }
}

#[cfg(any(test, feature = "arbitrary"))]
impl Arbitrary for UnitQuad {
    fn arbitrary<G: Gen>(g: &mut G) -> UnitQuad {
        use std::cmp;
        // FIXME: somehow this explicit usage of the `Rng` trait is required for
        // the `.gen_range` calls, even though `Rng: Gen`. The compiler
        // complains that the "source trait is private". Curiously, adding this
        // import here fixes the same situation in the `cubemap` module as well.
        let scale: u8 = {
            // scale >= 32 is invalid (overflow)
            // At scale >= 31 subdivision fails
            let max_scale = cmp::min(31, g.size()) as u8;
            g.gen_range(0, max_scale)
        };
        let max_offset = 2.pow(scale as u32);
        UnitQuad::new(scale, (
            g.gen_range(0, max_offset),
            g.gen_range(0, max_offset),
        ))
    }
}


#[cfg(test)]
mod test {
    pub use nalgebra::Vector2;
    pub use super::*;
    use quickcheck::{quickcheck, TestResult};
    use partition::Partition;

    partition_quickcheck!(unitquad_vec2_f32, UnitQuad, Vector2<f32>);
    partition_quickcheck!(unitquad_vec2_f64, UnitQuad, Vector2<f64>);

    #[test]
    fn unitquad_base_contains_region() {
        fn check(v: Vector2<f64>) -> TestResult {
            if v.x < 0.0 || v.x >= 1.0 || v.y < 0.0 || v.y >= 1.0 {
                TestResult::discard()
            } else {
                TestResult::from_bool(UnitQuad::new(0, (0, 0)).contains(&v))
            }
        }
        quickcheck(check as fn(Vector2<f64>) -> TestResult);
    }
}