spart/
geometry.rs

1//! ## Geometric Primitives and Operations for 2D and 3D Spaces
2//!
3//! This module provides geometric primitives and operations for both 2D and 3D spaces.
4//! It defines types such as `Point2D`, `Rectangle`, `Point3D`, and `Cube` along with their associated
5//! operations. These types form the basis for indexing and query algorithms in Spart.
6//!
7//! In addition to the basic types, the module defines several traits for operations such as
8//! bounding volume calculations and minimum distance computations.
9
10use ordered_float::OrderedFloat;
11#[cfg(feature = "serde")]
12use serde::{Deserialize, Serialize};
13use std::cmp::Ordering;
14use tracing::debug;
15
16// Import custom errors from the exceptions module.
17use crate::errors::SpartError;
18
19/// Represents a 2D point with an optional payload.
20///
21/// ### Example
22///
23/// ```
24/// use spart::geometry::Point2D;
25/// // Use an explicit type parameter (here, `()`) so that the type can be inferred.
26/// let pt: Point2D<()> = Point2D::new(1.0, 2.0, None);
27/// ```
28#[derive(Debug, Clone)]
29#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
30pub struct Point2D<T> {
31    /// The x-coordinate of the point.
32    pub x: f64,
33    /// The y-coordinate of the point.
34    pub y: f64,
35    /// Optional associated data.
36    pub data: Option<T>,
37}
38
39impl<T: PartialEq> PartialEq for Point2D<T> {
40    fn eq(&self, other: &Self) -> bool {
41        OrderedFloat(self.x) == OrderedFloat(other.x)
42            && OrderedFloat(self.y) == OrderedFloat(other.y)
43            && self.data == other.data
44    }
45}
46
47impl<T: Eq> Eq for Point2D<T> {}
48
49impl<T: PartialOrd> PartialOrd for Point2D<T> {
50    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
51        match (OrderedFloat(self.x), OrderedFloat(self.y))
52            .partial_cmp(&(OrderedFloat(other.x), OrderedFloat(other.y)))
53        {
54            Some(Ordering::Equal) => self.data.partial_cmp(&other.data),
55            other => other,
56        }
57    }
58}
59
60/// A trait for defining distance metrics.
61pub trait DistanceMetric<P> {
62    /// Computes the squared distance between two points.
63    fn distance_sq(p1: &P, p2: &P) -> f64;
64}
65
66/// A struct for Euclidean distance calculations.
67pub struct EuclideanDistance;
68
69impl<T> DistanceMetric<Point2D<T>> for EuclideanDistance {
70    fn distance_sq(p1: &Point2D<T>, p2: &Point2D<T>) -> f64 {
71        (p1.x - p2.x).powi(2) + (p1.y - p2.y).powi(2)
72    }
73}
74
75impl<T> DistanceMetric<Point3D<T>> for EuclideanDistance {
76    fn distance_sq(p1: &Point3D<T>, p2: &Point3D<T>) -> f64 {
77        (p1.x - p2.x).powi(2) + (p1.y - p2.y).powi(2) + (p1.z - p2.z).powi(2)
78    }
79}
80
81impl<T: Ord> Ord for Point2D<T> {
82    fn cmp(&self, other: &Self) -> Ordering {
83        match (OrderedFloat(self.x), OrderedFloat(self.y))
84            .cmp(&(OrderedFloat(other.x), OrderedFloat(other.y)))
85        {
86            Ordering::Equal => self.data.cmp(&other.data),
87            other => other,
88        }
89    }
90}
91
92impl<T> Point2D<T> {
93    /// Creates a new `Point2D` with the given coordinates and optional data.
94    ///
95    /// # Arguments
96    ///
97    /// * `x` - The x-coordinate.
98    /// * `y` - The y-coordinate.
99    /// * `data` - Optional data associated with the point.
100    ///
101    /// # Examples
102    ///
103    /// ```
104    /// use spart::geometry::Point2D;
105    /// let pt: Point2D<()> = Point2D::new(1.0, 2.0, None);
106    /// ```
107    pub fn new(x: f64, y: f64, data: Option<T>) -> Self {
108        let pt = Self { x, y, data };
109        debug!("Point2D::new() -> x: {}, y: {}", pt.x, pt.y);
110        pt
111    }
112
113    /// Computes the squared Euclidean distance between this point and another.
114    ///
115    /// # Arguments
116    ///
117    /// * `other` - The other point.
118    ///
119    /// # Examples
120    ///
121    /// ```
122    /// use spart::geometry::Point2D;
123    /// let a: Point2D<()> = Point2D::new(0.0, 0.0, None);
124    /// let b: Point2D<()> = Point2D::new(3.0, 4.0, None);
125    /// assert_eq!(a.distance_sq(&b), 25.0);
126    /// ```
127    pub fn distance_sq(&self, other: &Point2D<T>) -> f64 {
128        let dist = (self.x - other.x).powi(2) + (self.y - other.y).powi(2);
129        debug!(
130            "Point2D::distance_sq(): self: (x: {}, y: {}), other: (x: {}, y: {}), result: {}",
131            self.x, self.y, other.x, other.y, dist
132        );
133        dist
134    }
135}
136
137/// Represents a rectangle in 2D space.
138#[derive(Debug, Clone)]
139#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
140pub struct Rectangle {
141    /// The x-coordinate of the rectangle's top-left corner.
142    pub x: f64,
143    /// The y-coordinate of the rectangle's top-left corner.
144    pub y: f64,
145    /// The width of the rectangle.
146    pub width: f64,
147    /// The height of the rectangle.
148    pub height: f64,
149}
150
151impl Rectangle {
152    /// Determines if the rectangle contains the given point.
153    ///
154    /// # Arguments
155    ///
156    /// * `point` - The point to test.
157    ///
158    /// # Examples
159    ///
160    /// ```
161    /// use spart::geometry::{Rectangle, Point2D};
162    /// let rect = Rectangle { x: 0.0, y: 0.0, width: 10.0, height: 10.0 };
163    /// let pt: Point2D<()> = Point2D::new(5.0, 5.0, None);
164    /// assert!(rect.contains(&pt));
165    /// ```
166    pub fn contains<T>(&self, point: &Point2D<T>) -> bool {
167        let res = point.x >= self.x
168            && point.x <= self.x + self.width
169            && point.y >= self.y
170            && point.y <= self.y + self.height;
171        debug!("Rectangle::contains(): self: (x: {}, y: {}, w: {}, h: {}), point: (x: {}, y: {}), result: {}",
172            self.x, self.y, self.width, self.height, point.x, point.y, res);
173        res
174    }
175
176    /// Determines whether this rectangle intersects with another.
177    ///
178    /// # Arguments
179    ///
180    /// * `other` - The other rectangle.
181    ///
182    /// # Examples
183    ///
184    /// ```
185    /// use spart::geometry::Rectangle;
186    /// let a = Rectangle { x: 0.0, y: 0.0, width: 10.0, height: 10.0 };
187    /// let b = Rectangle { x: 5.0, y: 5.0, width: 10.0, height: 10.0 };
188    /// assert!(a.intersects(&b));
189    /// ```
190    pub fn intersects(&self, other: &Rectangle) -> bool {
191        let res = !(other.x > self.x + self.width
192            || other.x + other.width < self.x
193            || other.y > self.y + self.height
194            || other.y + other.height < self.y);
195        debug!("Rectangle::intersects(): self: (x: {}, y: {}, w: {}, h: {}), other: (x: {}, y: {}, w: {}, h: {}), result: {}",
196            self.x, self.y, self.width, self.height, other.x, other.y, other.width, other.height, res);
197        res
198    }
199
200    /// Computes the area of the rectangle.
201    ///
202    /// # Examples
203    ///
204    /// ```
205    /// use spart::geometry::Rectangle;
206    /// let rect = Rectangle { x: 0.0, y: 0.0, width: 4.0, height: 5.0 };
207    /// assert_eq!(rect.area(), 20.0);
208    /// ```
209    pub fn area(&self) -> f64 {
210        let area = self.width * self.height;
211        debug!(
212            "Rectangle::area(): (w: {}, h: {}) -> {}",
213            self.width, self.height, area
214        );
215        area
216    }
217
218    /// Computes the union of this rectangle with another.
219    ///
220    /// The union is defined as the smallest rectangle that completely contains both rectangles.
221    ///
222    /// # Arguments
223    ///
224    /// * `other` - The other rectangle.
225    ///
226    /// # Examples
227    ///
228    /// ```
229    /// use spart::geometry::Rectangle;
230    /// let a = Rectangle { x: 0.0, y: 0.0, width: 5.0, height: 5.0 };
231    /// let b = Rectangle { x: 3.0, y: 3.0, width: 5.0, height: 5.0 };
232    /// let union_rect = a.union(&b);
233    /// assert_eq!(union_rect.x, 0.0);
234    /// ```
235    pub fn union(&self, other: &Rectangle) -> Rectangle {
236        let x1 = self.x.min(other.x);
237        let y1 = self.y.min(other.y);
238        let x2 = (self.x + self.width).max(other.x + other.width);
239        let y2 = (self.y + self.height).max(other.y + other.height);
240
241        // Add small epsilon to width/height to account for floating-point precision errors
242        // This guarantees that corner points are always contained in the union
243        let eps = f64::EPSILON * 4.0 * (x2.abs() + x1.abs()).max(1.0);
244        let width = (x2 - x1) + eps;
245
246        let eps_y = f64::EPSILON * 4.0 * (y2.abs() + y1.abs()).max(1.0);
247        let height = (y2 - y1) + eps_y;
248
249        let union_rect = Rectangle {
250            x: x1,
251            y: y1,
252            width,
253            height,
254        };
255        debug!("Rectangle::union(): self: (x: {}, y: {}, w: {}, h: {}), other: (x: {}, y: {}, w: {}, h: {}), result: (x: {}, y: {}, w: {}, h: {})",
256            self.x, self.y, self.width, self.height, other.x, other.y, other.width, other.height,
257            union_rect.x, union_rect.y, union_rect.width, union_rect.height);
258        union_rect
259    }
260
261    /// Computes the enlargement needed to include another rectangle.
262    ///
263    /// The enlargement is defined as the difference between the area of the union and the area of this rectangle.
264    ///
265    /// # Arguments
266    ///
267    /// * `other` - The other rectangle.
268    ///
269    /// # Examples
270    ///
271    /// ```
272    /// use spart::geometry::Rectangle;
273    /// let a = Rectangle { x: 0.0, y: 0.0, width: 4.0, height: 4.0 };
274    /// let b = Rectangle { x: 2.0, y: 2.0, width: 4.0, height: 4.0 };
275    /// let enlargement = a.enlargement(&b);
276    /// assert!(enlargement >= 0.0);
277    /// ```
278    pub fn enlargement(&self, other: &Rectangle) -> f64 {
279        let union_rect = self.union(other);
280        let self_area = self.area();
281        let union_area = union_rect.area();
282        let extra = union_area - self_area;
283        debug!(
284            "Rectangle::enlargement(): self area: {}, union area: {}, enlargement: {}",
285            self_area, union_area, extra
286        );
287        extra
288    }
289}
290
291/// Represents a 3D point with an optional payload.
292///
293/// # Examples
294///
295/// ```
296/// use spart::geometry::Point3D;
297/// let pt: Point3D<()> = Point3D::new(1.0, 2.0, 3.0, None);
298/// ```
299#[derive(Debug, Clone)]
300#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
301pub struct Point3D<T> {
302    /// The x-coordinate of the point.
303    pub x: f64,
304    /// The y-coordinate of the point.
305    pub y: f64,
306    /// The z-coordinate of the point.
307    pub z: f64,
308    /// Optional associated data.
309    pub data: Option<T>,
310}
311
312impl<T: PartialEq> PartialEq for Point3D<T> {
313    fn eq(&self, other: &Self) -> bool {
314        OrderedFloat(self.x) == OrderedFloat(other.x)
315            && OrderedFloat(self.y) == OrderedFloat(other.y)
316            && OrderedFloat(self.z) == OrderedFloat(other.z)
317            && self.data == other.data
318    }
319}
320
321impl<T: Eq> Eq for Point3D<T> {}
322
323impl<T: PartialOrd> PartialOrd for Point3D<T> {
324    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
325        match (
326            OrderedFloat(self.x),
327            OrderedFloat(self.y),
328            OrderedFloat(self.z),
329        )
330            .partial_cmp(&(
331                OrderedFloat(other.x),
332                OrderedFloat(other.y),
333                OrderedFloat(other.z),
334            )) {
335            Some(Ordering::Equal) => self.data.partial_cmp(&other.data),
336            other => other,
337        }
338    }
339}
340
341impl<T: Ord> Ord for Point3D<T> {
342    fn cmp(&self, other: &Self) -> Ordering {
343        match (
344            OrderedFloat(self.x),
345            OrderedFloat(self.y),
346            OrderedFloat(self.z),
347        )
348            .cmp(&(
349                OrderedFloat(other.x),
350                OrderedFloat(other.y),
351                OrderedFloat(other.z),
352            )) {
353            Ordering::Equal => self.data.cmp(&other.data),
354            other => other,
355        }
356    }
357}
358
359impl<T> Point3D<T> {
360    /// Creates a new `Point3D` with the given coordinates and optional data.
361    ///
362    /// # Arguments
363    ///
364    /// * `x` - The x-coordinate.
365    /// * `y` - The y-coordinate.
366    /// * `z` - The z-coordinate.
367    /// * `data` - Optional data associated with the point.
368    ///
369    /// # Examples
370    ///
371    /// ```
372    /// use spart::geometry::Point3D;
373    /// let pt: Point3D<()> = Point3D::new(1.0, 2.0, 3.0, None);
374    /// ```
375    pub fn new(x: f64, y: f64, z: f64, data: Option<T>) -> Self {
376        let pt = Self { x, y, z, data };
377        debug!("Point3D::new() -> x: {}, y: {}, z: {}", pt.x, pt.y, pt.z);
378        pt
379    }
380
381    /// Computes the squared Euclidean distance between this point and another.
382    ///
383    /// # Arguments
384    ///
385    /// * `other` - The other 3D point.
386    ///
387    /// # Examples
388    ///
389    /// ```
390    /// use spart::geometry::Point3D;
391    /// let a: Point3D<()> = Point3D::new(0.0, 0.0, 0.0, None);
392    /// let b: Point3D<()> = Point3D::new(1.0, 2.0, 2.0, None);
393    /// assert_eq!(a.distance_sq(&b), 9.0);
394    /// ```
395    pub fn distance_sq(&self, other: &Point3D<T>) -> f64 {
396        let dist =
397            (self.x - other.x).powi(2) + (self.y - other.y).powi(2) + (self.z - other.z).powi(2);
398        debug!("Point3D::distance_sq(): self: (x: {}, y: {}, z: {}), other: (x: {}, y: {}, z: {}), result: {}",
399            self.x, self.y, self.z, other.x, other.y, other.z, dist);
400        dist
401    }
402}
403
404/// Represents a cube (or cuboid) in 3D space.
405#[derive(Debug, Clone)]
406#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
407pub struct Cube {
408    /// The x-coordinate of the cube's top-left-front corner.
409    pub x: f64,
410    /// The y-coordinate of the cube's top-left-front corner.
411    pub y: f64,
412    /// The z-coordinate of the cube's top-left-front corner.
413    pub z: f64,
414    /// The width of the cube.
415    pub width: f64,
416    /// The height of the cube.
417    pub height: f64,
418    /// The depth of the cube.
419    pub depth: f64,
420}
421
422impl Cube {
423    /// Determines if the cube contains the given 3D point.
424    ///
425    /// # Arguments
426    ///
427    /// * `point` - The 3D point to test.
428    ///
429    /// # Examples
430    ///
431    /// ```
432    /// use spart::geometry::{Cube, Point3D};
433    /// let cube = Cube { x: 0.0, y: 0.0, z: 0.0, width: 10.0, height: 10.0, depth: 10.0 };
434    /// let pt: Point3D<()> = Point3D::new(5.0, 5.0, 5.0, None);
435    /// assert!(cube.contains(&pt));
436    /// ```
437    pub fn contains<T>(&self, point: &Point3D<T>) -> bool {
438        let res = point.x >= self.x
439            && point.x <= self.x + self.width
440            && point.y >= self.y
441            && point.y <= self.y + self.height
442            && point.z >= self.z
443            && point.z <= self.z + self.depth;
444        debug!("Cube::contains(): self: (x: {}, y: {}, z: {}, w: {}, h: {}, d: {}), point: (x: {}, y: {}, z: {}), result: {}",
445            self.x, self.y, self.z, self.width, self.height, self.depth,
446            point.x, point.y, point.z, res);
447        res
448    }
449
450    /// Determines whether this cube intersects with another cube.
451    ///
452    /// # Arguments
453    ///
454    /// * `other` - The other cube.
455    ///
456    /// # Examples
457    ///
458    /// ```
459    /// use spart::geometry::Cube;
460    /// let a = Cube { x: 0.0, y: 0.0, z: 0.0, width: 5.0, height: 5.0, depth: 5.0 };
461    /// let b = Cube { x: 3.0, y: 3.0, z: 3.0, width: 5.0, height: 5.0, depth: 5.0 };
462    /// assert!(a.intersects(&b));
463    /// ```
464    pub fn intersects(&self, other: &Cube) -> bool {
465        let res = !(other.x > self.x + self.width
466            || other.x + other.width < self.x
467            || other.y > self.y + self.height
468            || other.y + other.height < self.y
469            || other.z > self.z + self.depth
470            || other.z + other.depth < self.z);
471        debug!("Cube::intersects(): self: (x: {}, y: {}, z: {}, w: {}, h: {}, d: {}), other: (x: {}, y: {}, z: {}, w: {}, h: {}, d: {}), result: {}",
472            self.x, self.y, self.z, self.width, self.height, self.depth,
473            other.x, other.y, other.z, other.width, other.height, other.depth, res);
474        res
475    }
476
477    /// Computes the volume of the cube.
478    ///
479    /// # Examples
480    ///
481    /// ```
482    /// use spart::geometry::Cube;
483    /// let cube = Cube { x: 0.0, y: 0.0, z: 0.0, width: 2.0, height: 3.0, depth: 4.0 };
484    /// assert_eq!(cube.area(), 24.0);
485    /// ```
486    pub fn area(&self) -> f64 {
487        let vol = self.width * self.height * self.depth;
488        debug!(
489            "Cube::area(): (w: {}, h: {}, d: {}) -> {}",
490            self.width, self.height, self.depth, vol
491        );
492        vol
493    }
494
495    /// Computes the union of this cube with another.
496    ///
497    /// The union is defined as the smallest cube that completely contains both cubes.
498    ///
499    /// # Arguments
500    ///
501    /// * `other` - The other cube.
502    ///
503    /// # Examples
504    ///
505    /// ```
506    /// use spart::geometry::Cube;
507    /// let a = Cube { x: 0.0, y: 0.0, z: 0.0, width: 3.0, height: 3.0, depth: 3.0 };
508    /// let b = Cube { x: 2.0, y: 2.0, z: 2.0, width: 3.0, height: 3.0, depth: 3.0 };
509    /// let union_cube = a.union(&b);
510    /// assert_eq!(union_cube.x, 0.0);
511    /// ```
512    pub fn union(&self, other: &Cube) -> Cube {
513        let x1 = self.x.min(other.x);
514        let y1 = self.y.min(other.y);
515        let z1 = self.z.min(other.z);
516        let x2 = (self.x + self.width).max(other.x + other.width);
517        let y2 = (self.y + self.height).max(other.y + other.height);
518        let z2 = (self.z + self.depth).max(other.z + other.depth);
519
520        // Add small epsilon to dimensions to account for floating-point precision errors
521        let eps_x = f64::EPSILON * 4.0 * (x2.abs() + x1.abs()).max(1.0);
522        let eps_y = f64::EPSILON * 4.0 * (y2.abs() + y1.abs()).max(1.0);
523        let eps_z = f64::EPSILON * 4.0 * (z2.abs() + z1.abs()).max(1.0);
524
525        let union_cube = Cube {
526            x: x1,
527            y: y1,
528            z: z1,
529            width: (x2 - x1) + eps_x,
530            height: (y2 - y1) + eps_y,
531            depth: (z2 - z1) + eps_z,
532        };
533        debug!("Cube::union(): self: (x: {}, y: {}, z: {}, w: {}, h: {}, d: {}), other: (x: {}, y: {}, z: {}, w: {}, h: {}, d: {}), result: (x: {}, y: {}, z: {}, w: {}, h: {}, d: {})",
534            self.x, self.y, self.z, self.width, self.height, self.depth,
535            other.x, other.y, other.z, other.width, other.height, other.depth,
536            union_cube.x, union_cube.y, union_cube.z, union_cube.width, union_cube.height, union_cube.depth);
537        union_cube
538    }
539
540    /// Computes the enlargement needed to include another cube.
541    ///
542    /// The enlargement is defined as the difference between the volume of the union and the volume of this cube.
543    ///
544    /// # Arguments
545    ///
546    /// * `other` - The other cube.
547    ///
548    /// # Examples
549    ///
550    /// ```
551    /// use spart::geometry::Cube;
552    /// let a = Cube { x: 0.0, y: 0.0, z: 0.0, width: 2.0, height: 2.0, depth: 2.0 };
553    /// let b = Cube { x: 1.0, y: 1.0, z: 1.0, width: 2.0, height: 2.0, depth: 2.0 };
554    /// let enlargement = a.enlargement(&b);
555    /// assert!(enlargement >= 0.0);
556    /// ```
557    pub fn enlargement(&self, other: &Cube) -> f64 {
558        let union_cube = self.union(other);
559        let self_area = self.area();
560        let union_area = union_cube.area();
561        let extra = union_area - self_area;
562        debug!(
563            "Cube::enlargement(): self volume: {}, union volume: {}, enlargement: {}",
564            self_area, union_area, extra
565        );
566        extra
567    }
568}
569
570/// Trait for types that can provide the center and extent along a specified dimension.
571pub trait BSPBounds {
572    /// The number of dimensions supported.
573    const DIM: usize;
574    /// Returns the center coordinate along the specified dimension.
575    ///
576    /// # Arguments
577    ///
578    /// * `dim` - The dimension index.
579    ///
580    /// # Errors
581    ///
582    /// Returns `SpartError::InvalidDimension` if `dim` is not within the valid range.
583    fn center(&self, dim: usize) -> Result<f64, SpartError>;
584    /// Returns the extent (width, height, or depth) along the specified dimension.
585    ///
586    /// # Arguments
587    ///
588    /// * `dim` - The dimension index.
589    ///
590    /// # Errors
591    ///
592    /// Returns `SpartError::InvalidDimension` if `dim` is not within the valid range.
593    fn extent(&self, dim: usize) -> Result<f64, SpartError>;
594}
595
596impl BSPBounds for Rectangle {
597    const DIM: usize = 2;
598    fn center(&self, dim: usize) -> Result<f64, SpartError> {
599        match dim {
600            0 => Ok(self.x + self.width / 2.0),
601            1 => Ok(self.y + self.height / 2.0),
602            _ => Err(SpartError::InvalidDimension {
603                requested: dim,
604                available: 2,
605            }),
606        }
607    }
608    fn extent(&self, dim: usize) -> Result<f64, SpartError> {
609        match dim {
610            0 => Ok(self.width),
611            1 => Ok(self.height),
612            _ => Err(SpartError::InvalidDimension {
613                requested: dim,
614                available: 2,
615            }),
616        }
617    }
618}
619
620impl BSPBounds for Cube {
621    const DIM: usize = 3;
622    fn center(&self, dim: usize) -> Result<f64, SpartError> {
623        match dim {
624            0 => Ok(self.x + self.width / 2.0),
625            1 => Ok(self.y + self.height / 2.0),
626            2 => Ok(self.z + self.depth / 2.0),
627            _ => Err(SpartError::InvalidDimension {
628                requested: dim,
629                available: 3,
630            }),
631        }
632    }
633    fn extent(&self, dim: usize) -> Result<f64, SpartError> {
634        match dim {
635            0 => Ok(self.width),
636            1 => Ok(self.height),
637            2 => Ok(self.depth),
638            _ => Err(SpartError::InvalidDimension {
639                requested: dim,
640                available: 3,
641            }),
642        }
643    }
644}
645
646/// Trait representing a bounding volume, such as a rectangle or cube.
647///
648/// This trait abstracts common operations for geometric volumes used in indexing.
649pub trait BoundingVolume: Clone {
650    /// Returns the area (or volume for 3D objects) of the bounding volume.
651    fn area(&self) -> f64;
652    /// Returns the smallest bounding volume that contains both `self` and `other`.
653    fn union(&self, other: &Self) -> Self;
654    /// Computes the enlargement required to include `other` in the bounding volume.
655    ///
656    /// By default, this is calculated as `union(other).area() - self.area()`.
657    fn enlargement(&self, other: &Self) -> f64 {
658        self.union(other).area() - self.area()
659    }
660    /// Determines whether the bounding volume intersects with another.
661    fn intersects(&self, other: &Self) -> bool;
662
663    /// Computes the overlap between two bounding volumes
664    fn overlap(&self, other: &Self) -> f64;
665
666    /// Computes the margin of a bounding box
667    fn margin(&self) -> f64;
668}
669
670impl BoundingVolume for Rectangle {
671    fn area(&self) -> f64 {
672        let a = Rectangle::area(self);
673        debug!("BoundingVolume (Rectangle)::area() -> {}", a);
674        a
675    }
676    fn union(&self, other: &Self) -> Self {
677        let u = Rectangle::union(self, other);
678        debug!("BoundingVolume (Rectangle)::union() computed.");
679        u
680    }
681    fn intersects(&self, other: &Self) -> bool {
682        let i = Rectangle::intersects(self, other);
683        debug!("BoundingVolume (Rectangle)::intersects() -> {}", i);
684        i
685    }
686    fn overlap(&self, other: &Self) -> f64 {
687        let overlap_x = (self.x + self.width).min(other.x + other.width) - self.x.max(other.x);
688        let overlap_y = (self.y + self.height).min(other.y + other.height) - self.y.max(other.y);
689        if overlap_x > 0.0 && overlap_y > 0.0 {
690            overlap_x * overlap_y
691        } else {
692            0.0
693        }
694    }
695
696    fn margin(&self) -> f64 {
697        2.0 * (self.width + self.height)
698    }
699}
700
701impl BoundingVolume for Cube {
702    fn area(&self) -> f64 {
703        let a = Cube::area(self);
704        debug!("BoundingVolume (Cube)::area() -> {}", a);
705        a
706    }
707    fn union(&self, other: &Self) -> Self {
708        let u = Cube::union(self, other);
709        debug!("BoundingVolume (Cube)::union() computed.");
710        u
711    }
712    fn intersects(&self, other: &Self) -> bool {
713        let i = Cube::intersects(self, other);
714        debug!("BoundingVolume (Cube)::intersects() -> {}", i);
715        i
716    }
717    fn overlap(&self, other: &Self) -> f64 {
718        let overlap_x = (self.x + self.width).min(other.x + other.width) - self.x.max(other.x);
719        let overlap_y = (self.y + self.height).min(other.y + other.height) - self.y.max(other.y);
720        let overlap_z = (self.z + self.depth).min(other.z + other.depth) - self.z.max(other.z);
721        if overlap_x > 0.0 && overlap_y > 0.0 && overlap_z > 0.0 {
722            overlap_x * overlap_y * overlap_z
723        } else {
724            0.0
725        }
726    }
727
728    fn margin(&self) -> f64 {
729        2.0 * (self.width + self.height + self.depth)
730    }
731}
732
733/// Represents an item in a heap, typically used for nearest neighbor or best-first search algorithms.
734///
735/// The `neg_distance` field is used to order items in a max-heap by their (negated) distance value.
736#[derive(Debug)]
737pub struct HeapItem<T: Clone> {
738    /// The negated distance, used for ordering.
739    pub neg_distance: OrderedFloat<f64>,
740    /// An optional 2D point associated with the heap item.
741    pub point_2d: Option<Point2D<T>>,
742    /// An optional 3D point associated with the heap item.
743    pub point_3d: Option<Point3D<T>>,
744}
745
746impl<T: Clone> PartialEq for HeapItem<T> {
747    fn eq(&self, other: &Self) -> bool {
748        self.neg_distance == other.neg_distance
749    }
750}
751
752impl<T: Clone> Eq for HeapItem<T> {}
753
754impl<T: Clone> PartialOrd for HeapItem<T> {
755    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
756        Some(self.cmp(other))
757    }
758}
759
760impl<T: Clone> Ord for HeapItem<T> {
761    fn cmp(&self, other: &Self) -> Ordering {
762        other.neg_distance.cmp(&self.neg_distance)
763    }
764}
765
766/// Trait for types that can compute the minimum distance to a given query.
767pub trait HasMinDistance<Q> {
768    /// Computes the minimum distance from the bounding volume to the given query.
769    fn min_distance(&self, query: &Q) -> f64;
770}
771
772/// Trait for constructing a bounding volume from a point and a radius.
773pub trait BoundingVolumeFromPoint<Q>: BoundingVolume {
774    /// Creates a bounding volume that encapsulates a point with the specified radius.
775    fn from_point_radius(query: &Q, radius: f64) -> Self;
776}
777
778impl<T> HasMinDistance<Point2D<T>> for Rectangle {
779    fn min_distance(&self, point: &Point2D<T>) -> f64 {
780        let dx = if point.x < self.x {
781            self.x - point.x
782        } else if point.x > self.x + self.width {
783            point.x - (self.x + self.width)
784        } else {
785            0.0
786        };
787        let dy = if point.y < self.y {
788            self.y - point.y
789        } else if point.y > self.y + self.height {
790            point.y - (self.y + self.height)
791        } else {
792            0.0
793        };
794        (dx * dx + dy * dy).sqrt()
795    }
796}
797
798impl<T> BoundingVolumeFromPoint<Point2D<T>> for Rectangle {
799    fn from_point_radius(query: &Point2D<T>, radius: f64) -> Self {
800        Rectangle {
801            x: query.x - radius,
802            y: query.y - radius,
803            width: 2.0 * radius,
804            height: 2.0 * radius,
805        }
806    }
807}
808
809impl<T> HasMinDistance<Point3D<T>> for Cube {
810    fn min_distance(&self, point: &Point3D<T>) -> f64 {
811        let dx = if point.x < self.x {
812            self.x - point.x
813        } else if point.x > self.x + self.width {
814            point.x - (self.x + self.width)
815        } else {
816            0.0
817        };
818        let dy = if point.y < self.y {
819            self.y - point.y
820        } else if point.y > self.y + self.height {
821            point.y - (self.y + self.height)
822        } else {
823            0.0
824        };
825        let dz = if point.z < self.z {
826            self.z - point.z
827        } else if point.z > self.z + self.depth {
828            point.z - (self.z + self.depth)
829        } else {
830            0.0
831        };
832        (dx * dx + dy * dy + dz * dz).sqrt()
833    }
834}
835
836impl<T> BoundingVolumeFromPoint<Point3D<T>> for Cube {
837    fn from_point_radius(query: &Point3D<T>, radius: f64) -> Self {
838        Cube {
839            x: query.x - radius,
840            y: query.y - radius,
841            z: query.z - radius,
842            width: 2.0 * radius,
843            height: 2.0 * radius,
844            depth: 2.0 * radius,
845        }
846    }
847}
spart/geometry.rs

spart/
geometry.rs
