bracket_geometry/
distance.rs

1use crate::prelude::{Point, Point3};
2use std::cmp::{max, min};
3
4/// Enumeration of available 2D Distance algorithms
5#[derive(Clone, Copy)]
6pub enum DistanceAlg {
7    /// Use the Pythagoras algorithm for determining distance - sqrt(A^2 + B^2)
8    Pythagoras,
9    /// Us the Pythagoras algorithm for distance, but omitting the square-root for a faster but squared result.
10    PythagorasSquared,
11    /// Use Manhattan distance (distance up plus distance along)
12    Manhattan,
13    /// Use Chebyshev distance (like Manhattan, but adds one to each entry)
14    Chebyshev,
15    /// Use a diagonal distance, the max of the x and y distances
16    Diagonal,
17}
18
19impl DistanceAlg {
20    /// Provides a 2D distance between points, using the specified algorithm.
21    pub fn distance2d(self, start: Point, end: Point) -> f32 {
22        match self {
23            DistanceAlg::Pythagoras => distance2d_pythagoras(start, end),
24            DistanceAlg::PythagorasSquared => distance2d_pythagoras_squared(start, end),
25            DistanceAlg::Manhattan => distance2d_manhattan(start, end),
26            DistanceAlg::Chebyshev => distance2d_chebyshev(start, end),
27            DistanceAlg::Diagonal => distance2d_diagonal(start, end),
28        }
29    }
30    /// Provides a 3D distance between points, using the specified algorithm.
31    pub fn distance3d(self, start: Point3, end: Point3) -> f32 {
32        match self {
33            DistanceAlg::Pythagoras => distance3d_pythagoras(start, end),
34            DistanceAlg::PythagorasSquared => distance3d_pythagoras_squared(start, end),
35            DistanceAlg::Manhattan => distance3d_manhattan(start, end),
36            DistanceAlg::Chebyshev => distance3d_pythagoras(start, end),
37            DistanceAlg::Diagonal => distance3d_diagonal(start, end),
38        }
39    }
40}
41
42/// Calculates a Pythagoras distance between two points, and skips the square root for speed.
43fn distance2d_pythagoras_squared(start: Point, end: Point) -> f32 {
44    let dx = (max(start.x, end.x) - min(start.x, end.x)) as f32;
45    let dy = (max(start.y, end.y) - min(start.y, end.y)) as f32;
46    (dx * dx) + (dy * dy)
47}
48
49/// Calculates a Manhattan distance between two points
50fn distance2d_manhattan(start: Point, end: Point) -> f32 {
51    let dx = (max(start.x, end.x) - min(start.x, end.x)) as f32;
52    let dy = (max(start.y, end.y) - min(start.y, end.y)) as f32;
53    dx + dy
54}
55
56/// Calculates a Manhattan distance between two 3D points
57fn distance3d_manhattan(start: Point3, end: Point3) -> f32 {
58    let dx = (max(start.x, end.x) - min(start.x, end.x)) as f32;
59    let dy = (max(start.y, end.y) - min(start.y, end.y)) as f32;
60    let dz = (max(start.z, end.z) - min(start.z, end.z)) as f32;
61    dx + dy + dz
62}
63
64/// Calculates a Chebyshev distance between two points
65/// See: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
66fn distance2d_chebyshev(start: Point, end: Point) -> f32 {
67    let dx = (max(start.x, end.x) - min(start.x, end.x)) as f32;
68    let dy = (max(start.y, end.y) - min(start.y, end.y)) as f32;
69    if dx > dy {
70        (dx - dy) + 1.0 * dy
71    } else {
72        (dy - dx) + 1.0 * dx
73    }
74}
75
76/// Calculates a Pythagoras distance between two 3D points.
77fn distance3d_pythagoras_squared(start: Point3, end: Point3) -> f32 {
78    let dx = (max(start.x, end.x) - min(start.x, end.x)) as f32;
79    let dy = (max(start.y, end.y) - min(start.y, end.y)) as f32;
80    let dz = (max(start.z, end.z) - min(start.z, end.z)) as f32;
81    (dx * dx) + (dy * dy) + (dz * dz)
82}
83
84/// Calculates a Pythagoras distance between two points.
85fn distance2d_pythagoras(start: Point, end: Point) -> f32 {
86    let dsq = distance2d_pythagoras_squared(start, end);
87    f32::sqrt(dsq)
88}
89
90/// Calculates a Pythagoras distance between two 3D points.
91fn distance3d_pythagoras(start: Point3, end: Point3) -> f32 {
92    let dsq = distance3d_pythagoras_squared(start, end);
93    f32::sqrt(dsq)
94}
95
96// Calculates a diagonal distance
97fn distance2d_diagonal(start: Point, end: Point) -> f32 {
98    i32::max((start.x - end.x).abs(), (start.y - end.y).abs()) as f32
99}
100
101fn distance3d_diagonal(start: Point3, end: Point3) -> f32 {
102    i32::max(
103        (start.x - end.x).abs(),
104        i32::max((start.y - end.y).abs(), (start.z - end.z).abs()),
105    ) as f32
106}
107
108#[cfg(test)]
109mod tests {
110    use crate::prelude::{DistanceAlg, Point, Point3};
111
112    #[test]
113    fn test_pythagoras_distance() {
114        let mut d = DistanceAlg::Pythagoras.distance2d(Point::new(0, 0), Point::new(5, 0));
115        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
116
117        d = DistanceAlg::Pythagoras.distance2d(Point::new(0, 0), Point::new(-5, 0));
118        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
119
120        d = DistanceAlg::Pythagoras.distance2d(Point::new(0, 0), Point::new(0, 5));
121        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
122
123        d = DistanceAlg::Pythagoras.distance2d(Point::new(0, 0), Point::new(0, -5));
124        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
125
126        d = DistanceAlg::Pythagoras.distance2d(Point::new(0, 0), Point::new(5, 5));
127        assert!(f32::abs(d - 7.071_068) < std::f32::EPSILON);
128    }
129
130    #[test]
131    fn test_pythagoras_distance3d() {
132        let mut d = DistanceAlg::Pythagoras.distance3d(Point3::new(0, 0, 0), Point3::new(5, 0, 0));
133        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
134
135        d = DistanceAlg::Pythagoras.distance3d(Point3::new(0, 0, 0), Point3::new(-5, 0, 0));
136        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
137
138        d = DistanceAlg::Pythagoras.distance3d(Point3::new(0, 0, 0), Point3::new(5, 5, 5));
139        assert!(f32::abs(d - 8.660_254_5) < std::f32::EPSILON);
140    }
141
142    #[test]
143    fn test_pythagoras_squared_distance() {
144        let mut d = DistanceAlg::PythagorasSquared.distance2d(Point::new(0, 0), Point::new(5, 0));
145        assert!(f32::abs(d - 25.0) < std::f32::EPSILON);
146
147        d = DistanceAlg::PythagorasSquared.distance2d(Point::new(0, 0), Point::new(-5, 0));
148        assert!(f32::abs(d - 25.0) < std::f32::EPSILON);
149
150        d = DistanceAlg::PythagorasSquared.distance2d(Point::new(0, 0), Point::new(0, 5));
151        assert!(f32::abs(d - 25.0) < std::f32::EPSILON);
152
153        d = DistanceAlg::PythagorasSquared.distance2d(Point::new(0, 0), Point::new(0, -5));
154        assert!(f32::abs(d - 25.0) < std::f32::EPSILON);
155
156        d = DistanceAlg::PythagorasSquared.distance2d(Point::new(0, 0), Point::new(5, 5));
157        assert!(f32::abs(d - 50.0) < std::f32::EPSILON);
158    }
159
160    #[test]
161    fn test_pythagoras_squared_distance3d() {
162        let mut d =
163            DistanceAlg::PythagorasSquared.distance3d(Point3::new(0, 0, 0), Point3::new(5, 0, 0));
164        assert!(f32::abs(d - 25.0) < std::f32::EPSILON);
165
166        d = DistanceAlg::PythagorasSquared.distance3d(Point3::new(0, 0, 0), Point3::new(-5, 0, 0));
167        assert!(f32::abs(d - 25.0) < std::f32::EPSILON);
168
169        d = DistanceAlg::PythagorasSquared.distance3d(Point3::new(0, 0, 0), Point3::new(5, 5, 5));
170        assert!(f32::abs(d - 75.0) < std::f32::EPSILON);
171    }
172
173    #[test]
174    fn test_manhattan_distance() {
175        let mut d = DistanceAlg::Manhattan.distance2d(Point::new(0, 0), Point::new(5, 0));
176        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
177
178        d = DistanceAlg::Manhattan.distance2d(Point::new(0, 0), Point::new(-5, 0));
179        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
180
181        d = DistanceAlg::Manhattan.distance2d(Point::new(0, 0), Point::new(0, 5));
182        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
183
184        d = DistanceAlg::Manhattan.distance2d(Point::new(0, 0), Point::new(0, -5));
185        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
186
187        d = DistanceAlg::Manhattan.distance2d(Point::new(0, 0), Point::new(5, 5));
188        assert!(f32::abs(d - 10.0) < std::f32::EPSILON);
189    }
190
191    #[test]
192    fn test_manhattan_distance3d() {
193        let mut d = DistanceAlg::Manhattan.distance3d(Point3::new(0, 0, 0), Point3::new(5, 0, 0));
194        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
195
196        d = DistanceAlg::Manhattan.distance3d(Point3::new(0, 0, 0), Point3::new(-5, 0, 0));
197        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
198
199        d = DistanceAlg::Manhattan.distance3d(Point3::new(0, 0, 0), Point3::new(5, 5, 5));
200        assert!(f32::abs(d - 15.0) < std::f32::EPSILON);
201    }
202
203    #[test]
204    fn test_chebyshev_distance() {
205        let mut d = DistanceAlg::Chebyshev.distance2d(Point::new(0, 0), Point::new(5, 0));
206        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
207
208        d = DistanceAlg::Chebyshev.distance2d(Point::new(0, 0), Point::new(-5, 0));
209        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
210
211        d = DistanceAlg::Chebyshev.distance2d(Point::new(0, 0), Point::new(0, 5));
212        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
213
214        d = DistanceAlg::Chebyshev.distance2d(Point::new(0, 0), Point::new(0, -5));
215        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
216
217        d = DistanceAlg::Chebyshev.distance2d(Point::new(0, 0), Point::new(5, 5));
218        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
219    }
220
221    #[test]
222    fn test_algorithm_from_shared_reference() {
223        let mut algorithm = DistanceAlg::Chebyshev;
224        let mut d = algorithm.distance2d(Point::new(0, 0), Point::new(5, 5));
225        assert!(f32::abs(d - 5.0) < std::f32::EPSILON);
226
227        algorithm = DistanceAlg::Manhattan;
228        d = algorithm.distance2d(Point::new(0, 0), Point::new(5, 5));
229        assert!(f32::abs(d - 10.0) < std::f32::EPSILON);
230
231        let shared_ref = &algorithm;
232        d = shared_ref.distance2d(Point::new(0, 0), Point::new(5, 5));
233        assert!(f32::abs(d - 10.0) < std::f32::EPSILON);
234    }
235}
bracket_geometry/distance.rs

bracket_geometry/
distance.rs
