rgeometry/algorithms/
zhash.rs

1use crate::data::Point;
2
3///////////////////////////////////////////////////////////////////////////////
4// Z-Order Hash
5
6// A        = aaaa =  a a a a
7// B        = bbbb = b b b b
8// zhash_pair(a,b) = babababa
9
10#[derive(Debug)]
11pub struct ZHashBox<'a, T> {
12  pub min_x: &'a T,
13  pub max_x: &'a T,
14  pub min_y: &'a T,
15  pub max_y: &'a T,
16}
17impl<T> Copy for ZHashBox<'_, T> {}
18
19impl<'a, T> Clone for ZHashBox<'a, T> {
20  fn clone(&self) -> ZHashBox<'a, T> {
21    *self
22  }
23}
24
25pub trait ZHashable: Sized {
26  type ZHashKey: Copy;
27  fn zhash_key(zbox: ZHashBox<'_, Self>) -> Self::ZHashKey;
28  fn zhash_fn(key: Self::ZHashKey, point: &Point<Self>) -> u64;
29}
30
31impl ZHashable for f64 {
32  type ZHashKey = (f64, f64, f64, f64);
33  fn zhash_key(zbox: ZHashBox<'_, f64>) -> Self::ZHashKey {
34    let width = zbox.max_x - zbox.min_x;
35    let height = zbox.max_y - zbox.min_y;
36    (*zbox.min_x, *zbox.min_y, width, height)
37  }
38  fn zhash_fn(key: Self::ZHashKey, point: &Point<Self>) -> u64 {
39    let (min_x, min_y, width, height) = key;
40    let z_hash_max = f64::from(u32::MAX);
41    let x = ((point.x_coord() - min_x) / width * z_hash_max) as u32;
42    let y = ((point.y_coord() - min_y) / height * z_hash_max) as u32;
43    zhash_pair(x, y)
44  }
45}
46
47impl ZHashable for i64 {
48  type ZHashKey = (i64, i64, u32, u32);
49  fn zhash_key(zbox: ZHashBox<'_, i64>) -> Self::ZHashKey {
50    let width = zbox.max_x.wrapping_sub(*zbox.min_x) as u64;
51    let height = zbox.max_y.wrapping_sub(*zbox.min_y) as u64;
52    let x_r_shift = 32u32.saturating_sub(width.leading_zeros());
53    let y_r_shift = 32u32.saturating_sub(height.leading_zeros());
54    (*zbox.min_x, *zbox.min_y, x_r_shift, y_r_shift)
55  }
56  fn zhash_fn(key: Self::ZHashKey, point: &Point<Self>) -> u64 {
57    let (min_x, min_y, x_r_shift, y_r_shift) = key;
58    let x = ((point.x_coord().wrapping_sub(min_x) as u64) >> x_r_shift) as u32;
59    let y = ((point.y_coord().wrapping_sub(min_y) as u64) >> y_r_shift) as u32;
60    zhash_pair(x, y)
61  }
62}
63
64impl ZHashable for i8 {
65  type ZHashKey = (i8, i8);
66  fn zhash_key(zbox: ZHashBox<'_, i8>) -> Self::ZHashKey {
67    (*zbox.min_x, *zbox.min_y)
68  }
69  fn zhash_fn(key: Self::ZHashKey, point: &Point<Self>) -> u64 {
70    let (min_x, min_y) = key;
71    let x = point.x_coord().abs_diff(min_x) as u32;
72    let y = point.y_coord().abs_diff(min_y) as u32;
73    // dbg!(point.x_coord(), min_x, x);
74    // dbg!(point.y_coord(), min_y, y);
75    zhash_pair(x, y)
76  }
77}
78
79impl ZHashable for u64 {
80  type ZHashKey = (u64, u64, u32, u32);
81  fn zhash_key(zbox: ZHashBox<'_, u64>) -> Self::ZHashKey {
82    let width = zbox.max_x - zbox.min_x;
83    let height = zbox.max_y - zbox.min_y;
84    let x_r_shift = 32u32.saturating_sub(width.leading_zeros());
85    let y_r_shift = 32u32.saturating_sub(height.leading_zeros());
86    (*zbox.min_x, *zbox.min_y, x_r_shift, y_r_shift)
87  }
88  fn zhash_fn(key: Self::ZHashKey, point: &Point<Self>) -> u64 {
89    let (min_x, min_y, x_r_shift, y_r_shift) = key;
90    let x = ((*point.x_coord() - min_x) >> x_r_shift) as u32;
91    let y = ((*point.y_coord() - min_y) >> y_r_shift) as u32;
92    zhash_pair(x, y)
93  }
94}
95
96impl ZHashable for u32 {
97  type ZHashKey = ();
98  fn zhash_key(_zbox: ZHashBox<'_, u32>) -> Self::ZHashKey {}
99  fn zhash_fn(_key: Self::ZHashKey, point: &Point<Self>) -> u64 {
100    zhash_pair(*point.x_coord(), *point.y_coord())
101  }
102}
103
104pub fn zunhash_pair(w: u64) -> (u32, u32) {
105  (zunhash_u32(w), zunhash_u32(w >> 1))
106}
107
108fn zunhash_u32(w: u64) -> u32 {
109  let w = w & 0x5555555555555555;
110  let w = (w | w >> 1) & 0x3333333333333333;
111  let w = (w | w >> 2) & 0x0F0F0F0F0F0F0F0F;
112  let w = (w | w >> 4) & 0x00FF00FF00FF00FF;
113  let w = (w | w >> 8) & 0x0000FFFF0000FFFF;
114  let w = (w | w >> 16) & 0x00000000FFFFFFFF;
115  w as u32
116}
117
118pub fn zhash_pair(a: u32, b: u32) -> u64 {
119  zhash_u32(a) | zhash_u32(b) << 1
120}
121
122fn zhash_u32(w: u32) -> u64 {
123  let w = w as u64; // & 0x00000000FFFFFFFF;
124  let w = (w | w << 16) & 0x0000FFFF0000FFFF;
125  let w = (w | w << 8) & 0x00FF00FF00FF00FF;
126  let w = (w | w << 4) & 0x0F0F0F0F0F0F0F0F;
127  let w = (w | w << 2) & 0x3333333333333333;
128  (w | w << 1) & 0x5555555555555555
129}
130
131#[cfg(test)]
132#[cfg(not(tarpaulin_include))]
133mod tests {
134  use super::*;
135  use crate::data::Triangle;
136
137  use proptest::prelude::*;
138  use rand::SeedableRng;
139  use test_strategy::proptest;
140
141  #[proptest]
142  fn hash_unhash_prop(a: u32, b: u32) {
143    prop_assert_eq!(zunhash_pair(zhash_pair(a, b)), (a, b))
144  }
145
146  #[proptest]
147  fn cmp_prop_i8(trig: Triangle<i8>) {
148    let (min, max) = trig.view().bounding_box();
149    let zbox = ZHashBox {
150      min_x: min.x_coord(),
151      max_x: max.x_coord(),
152      min_y: min.y_coord(),
153      max_y: max.y_coord(),
154    };
155    let key = ZHashable::zhash_key(zbox);
156    let mut rng = rand::rngs::SmallRng::seed_from_u64(0);
157    let middle = trig.view().rejection_sampling(&mut rng);
158    let min_hash = ZHashable::zhash_fn(key, &min);
159    let max_hash = ZHashable::zhash_fn(key, &max);
160    let mid_hash = ZHashable::zhash_fn(key, &middle);
161    prop_assert!(min_hash <= mid_hash);
162    prop_assert!(mid_hash <= max_hash);
163  }
164
165  #[proptest]
166  fn cmp_prop_i64(trig: Triangle<i64>) {
167    let (min, max) = trig.view().bounding_box();
168    let zbox = ZHashBox {
169      min_x: min.x_coord(),
170      max_x: max.x_coord(),
171      min_y: min.y_coord(),
172      max_y: max.y_coord(),
173    };
174    let key = ZHashable::zhash_key(zbox);
175    let mut rng = rand::rngs::SmallRng::seed_from_u64(0);
176    let middle = trig.view().rejection_sampling(&mut rng);
177    let min_hash = ZHashable::zhash_fn(key, &min);
178    let max_hash = ZHashable::zhash_fn(key, &max);
179    let mid_hash = ZHashable::zhash_fn(key, &middle);
180    prop_assert!(min_hash <= mid_hash);
181    prop_assert!(mid_hash <= max_hash);
182  }
183}
rgeometry/algorithms/zhash.rs

rgeometry/algorithms/
zhash.rs
