rstar/primitives/
line.rs

1use crate::aabb::AABB;
2use crate::envelope::Envelope;
3use crate::object::PointDistance;
4use crate::object::RTreeObject;
5use crate::point::{Point, PointExt};
6use num_traits::{One, Zero};
7
8/// A line defined by a start and and end point.
9///
10/// This struct can be inserted directly into an r-tree.
11/// # Type parameters
12/// `P`: The line's [Point] type.
13///
14/// # Example
15/// ```
16/// use rstar::primitives::Line;
17/// use rstar::{RTree, RTreeObject};
18///
19/// let line_1 = Line::new([0.0, 0.0], [1.0, 1.0]);
20/// let line_2 = Line::new([0.0, 0.0], [-1.0, 1.0]);
21/// let tree = RTree::bulk_load(vec![line_1, line_2]);
22///
23/// assert!(tree.contains(&line_1));
24/// ```
25#[derive(Debug, Clone, Copy, Eq, PartialEq, Ord, PartialOrd)]
26#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
27pub struct Line<P>
28where
29    P: Point,
30{
31    /// The line's start point
32    pub from: P,
33    /// The line's end point.
34    pub to: P,
35}
36
37impl<P> Line<P>
38where
39    P: Point,
40{
41    /// Creates a new line between two points.
42    pub fn new(from: P, to: P) -> Self {
43        Line { from, to }
44    }
45}
46
47impl<P> RTreeObject for Line<P>
48where
49    P: Point,
50{
51    type Envelope = AABB<P>;
52
53    fn envelope(&self) -> Self::Envelope {
54        AABB::from_corners(self.from.clone(), self.to.clone())
55    }
56}
57
58impl<P> Line<P>
59where
60    P: Point,
61{
62    /// Returns the squared length of this line.
63    ///
64    /// # Example
65    /// ```
66    /// use rstar::primitives::Line;
67    ///
68    /// let line = Line::new([3, 3], [7, 6]);
69    /// assert_eq!(line.length_2(), 25);
70    /// ```
71    pub fn length_2(&self) -> P::Scalar {
72        self.from.sub(&self.to).length_2()
73    }
74
75    fn project_point(&self, query_point: &P) -> P::Scalar {
76        let (ref p1, ref p2) = (self.from.clone(), self.to.clone());
77        let dir = p2.sub(p1);
78        query_point.sub(p1).dot(&dir) / dir.length_2()
79    }
80
81    /// Returns the nearest point on this line relative to a given point.
82    ///
83    /// # Example
84    /// ```
85    /// use rstar::primitives::Line;
86    ///
87    /// let line = Line::new([0.0, 0.0], [1., 1.]);
88    /// assert_eq!(line.nearest_point(&[0.0, 0.0]), [0.0, 0.0]);
89    /// assert_eq!(line.nearest_point(&[1.0, 0.0]), [0.5, 0.5]);
90    /// assert_eq!(line.nearest_point(&[10., 12.]), [1.0, 1.0]);
91    /// ```
92    pub fn nearest_point(&self, query_point: &P) -> P {
93        let (p1, p2) = (self.from.clone(), self.to.clone());
94        let dir = p2.sub(&p1);
95        let s = self.project_point(query_point);
96        if P::Scalar::zero() < s && s < One::one() {
97            p1.add(&dir.mul(s))
98        } else if s <= P::Scalar::zero() {
99            p1
100        } else {
101            p2
102        }
103    }
104}
105
106impl<P> PointDistance for Line<P>
107where
108    P: Point,
109{
110    fn distance_2(
111        &self,
112        point: &<Self::Envelope as Envelope>::Point,
113    ) -> <<Self::Envelope as Envelope>::Point as Point>::Scalar {
114        self.nearest_point(point).sub(point).length_2()
115    }
116}
117
118#[cfg(test)]
119mod test {
120    use super::Line;
121    use crate::object::PointDistance;
122    use approx::*;
123
124    #[test]
125    fn edge_distance() {
126        let edge = Line::new([0.5, 0.5], [0.5, 2.0]);
127
128        assert_abs_diff_eq!(edge.distance_2(&[0.5, 0.5]), 0.0);
129        assert_abs_diff_eq!(edge.distance_2(&[0.0, 0.5]), 0.5 * 0.5);
130        assert_abs_diff_eq!(edge.distance_2(&[0.5, 1.0]), 0.0);
131        assert_abs_diff_eq!(edge.distance_2(&[0.0, 0.0]), 0.5);
132        assert_abs_diff_eq!(edge.distance_2(&[0.0, 1.0]), 0.5 * 0.5);
133        assert_abs_diff_eq!(edge.distance_2(&[1.0, 1.0]), 0.5 * 0.5);
134        assert_abs_diff_eq!(edge.distance_2(&[1.0, 3.0]), 0.5 * 0.5 + 1.0);
135    }
136
137    #[test]
138    fn length_2() {
139        let line = Line::new([1, -1], [5, 5]);
140        assert_eq!(line.length_2(), 16 + 36);
141    }
142}
rstar/primitives/line.rs

rstar/primitives/
line.rs
