spaceindex/geometry/
line_segment.rs

1use crate::geometry::{
2    check_dimensions_match, min_distance_point_line, Point, Region, Shape, Shapelike,
3    ShapelikeError,
4};
5
6#[derive(Debug, Clone, PartialEq)]
7pub struct LineSegment {
8    start: Point,
9    end: Point,
10}
11
12impl LineSegment {
13    pub fn new(start: Point, end: Point) -> Self {
14        // TODO: consider making this function return a result and not panicking
15        assert_eq!(start.get_dimension(), end.get_dimension());
16
17        Self { start, end }
18    }
19
20    #[inline(always)]
21    pub fn get_coordinate(&self, index: usize) -> (f64, f64) {
22        (
23            self.start.get_coordinate(index),
24            self.end.get_coordinate(index),
25        )
26    }
27
28    pub fn get_points(&self) -> (&Point, &Point) {
29        (&self.start, &self.end)
30    }
31
32    pub fn coordinate_iter(&self) -> impl Iterator<Item = (f64, f64)> + '_ {
33        self.start.coordinate_iter().zip(self.end.coordinate_iter())
34    }
35
36    /// Returns double the area of the triangle created by points `a`, `b`, and `c`.
37    #[inline(always)]
38    fn double_area_triangle(a: &Point, b: &Point, c: &Point) -> f64 {
39        ((b.get_coordinate(0) - a.get_coordinate(0)) * (c.get_coordinate(1) - a.get_coordinate(1)))
40            - ((c.get_coordinate(0) - a.get_coordinate(0))
41                * (b.get_coordinate(1) - a.get_coordinate(1)))
42    }
43
44    /// Returns `true` if [`Point`] `self` is to the left of the segment (a, b).
45    #[inline(always)]
46    fn left_of(a: &Point, b: &Point, c: &Point) -> bool {
47        Self::double_area_triangle(a, b, c) > 0.0
48    }
49
50    /// Returns `true` if `a`, `b`, and `c` are collinear.
51    #[inline(always)]
52    fn collinear(a: &Point, b: &Point, c: &Point) -> bool {
53        Self::double_area_triangle(a, b, c) == 0.0
54    }
55
56    /// Determine whether the segments (a, b) and (c, d) intersect (excluding endpoints).
57    #[inline(always)]
58    fn intersects_proper(a: &Point, b: &Point, c: &Point, d: &Point) -> bool {
59        if Self::collinear(a, b, c)
60            || Self::collinear(a, b, d)
61            || Self::collinear(c, d, a)
62            || Self::collinear(c, d, b)
63        {
64            return false;
65        }
66
67        (Self::left_of(a, b, c) ^ Self::left_of(a, b, d))
68            && (Self::left_of(c, d, a) ^ Self::left_of(c, d, b))
69    }
70
71    /// Assuming `a`, `b`, and `c` are collinear, determine whether `c` is between `a` and `b`.
72    fn between(a: &Point, b: &Point, c: &Point) -> bool {
73        fn _between(x1: f64, x2: f64, x3: f64) -> bool {
74            ((x1 <= x3) && (x3 <= x2)) || ((x1 >= x3) && (x3 >= x2))
75        }
76
77        if !Self::collinear(a, b, c) {
78            return false;
79        }
80
81        if (a.get_coordinate(0) - b.get_coordinate(0)).abs() > std::f64::EPSILON {
82            // If `a` and `b` are not on the same vertical, compare along the x-axis.
83            _between(
84                a.get_coordinate(0),
85                b.get_coordinate(0),
86                c.get_coordinate(0),
87            )
88        } else {
89            // other we have a vertical segment, so compare along the y-axis.
90            _between(
91                a.get_coordinate(1),
92                b.get_coordinate(1),
93                c.get_coordinate(1),
94            )
95        }
96    }
97
98    #[inline(always)]
99    fn intersects(a: &Point, b: &Point, c: &Point, d: &Point) -> bool {
100        Self::intersects_proper(a, b, c, d)
101            || Self::between(a, b, c)
102            || Self::between(a, b, d)
103            || Self::between(c, d, a)
104            || Self::between(c, d, b)
105    }
106}
107
108impl Shapelike for LineSegment {
109    fn get_center(&self) -> Point {
110        let mut coordinates = Vec::with_capacity(self.get_dimension());
111
112        for (start_coord, end_coord) in self.coordinate_iter() {
113            coordinates
114                .push(((start_coord - end_coord).abs() / 2.0) + f64::min(start_coord, end_coord));
115        }
116
117        Point::new(coordinates)
118    }
119
120    fn get_dimension(&self) -> usize {
121        self.start.get_dimension()
122    }
123
124    fn get_min_bounding_region(&self) -> Region {
125        let mut coordinates = Vec::with_capacity(self.get_dimension());
126
127        for (start_coord, end_coord) in self.coordinate_iter() {
128            coordinates.push((
129                f64::min(start_coord, end_coord),
130                f64::max(start_coord, end_coord),
131            ));
132        }
133
134        Region::new(coordinates)
135    }
136
137    fn get_area(&self) -> f64 {
138        0.0
139    }
140
141    fn get_min_distance(&self, other: &Shape) -> Result<f64, ShapelikeError> {
142        check_dimensions_match(self, other)?;
143
144        match other {
145            Shape::Point(point) => min_distance_point_line(point, self),
146            Shape::LineSegment(_) => Err(ShapelikeError::UnsupportedOperation),
147            Shape::Region(_) => Err(ShapelikeError::UnsupportedOperation),
148        }
149    }
150
151    fn intersects_line_segment(&self, line: &LineSegment) -> Result<bool, ShapelikeError> {
152        if self.get_dimension() != 2 {
153            return Err(ShapelikeError::UnexpectedDimension(self.get_dimension(), 2));
154        }
155
156        check_dimensions_match(self, line)?;
157
158        Ok(Self::intersects(
159            &self.start,
160            &self.end,
161            &line.start,
162            &line.end,
163        ))
164    }
165
166    fn intersects_region(&self, region: &Region) -> Result<bool, ShapelikeError> {
167        if self.get_dimension() != 2 {
168            return Err(ShapelikeError::UnexpectedDimension(self.get_dimension(), 2));
169        }
170
171        check_dimensions_match(self, region)?;
172
173        // defer to the `Region` implementation
174        region.intersects_line_segment(self)
175    }
176}
spaceindex/geometry/line_segment.rs

spaceindex/geometry/
line_segment.rs
