street_engine/core/geometry/
line_segment.rs

1use super::site::Site;
2
3/// Representation of a line segment.
4#[derive(Debug, Clone)]
5pub struct LineSegment(pub Site, pub Site);
6
7impl LineSegment {
8    /// Create a line segment from two sites.
9    pub fn new(start: Site, end: Site) -> Self {
10        Self(start, end)
11    }
12
13    /// Calculate the intersection of two line segments.
14    /// If the intersection is outside the line segments or not exist, return None.
15    pub fn get_intersection(&self, other: &Self) -> Option<Site> {
16        let (x0, y0) = (self.0.x, self.0.y);
17        let (x1, y1) = (self.1.x, self.1.y);
18        let (x2, y2) = (other.0.x, other.0.y);
19        let (x3, y3) = (other.1.x, other.1.y);
20
21        let a1 = y1 - y0;
22        let b1 = x0 - x1;
23        let c1 = x1 * y0 - x0 * y1;
24        let r3 = a1 * x2 + b1 * y2 + c1;
25        let r4 = a1 * x3 + b1 * y3 + c1;
26        if r3 * r4 > 0.0 {
27            return None;
28        }
29
30        let a2 = y3 - y2;
31        let b2 = x2 - x3;
32        let c2 = x3 * y2 - x2 * y3;
33        let r1 = a2 * x0 + b2 * y0 + c2;
34        let r2 = a2 * x1 + b2 * y1 + c2;
35        if r1 * r2 > 0.0 {
36            return None;
37        }
38
39        let denom = a1 * b2 - a2 * b1;
40        if denom == 0.0 {
41            return None;
42        }
43        let x = (b1 * c2 - b2 * c1) / denom;
44        let y = (a2 * c1 - a1 * c2) / denom;
45        Some(Site::new(x, y))
46    }
47
48    /// Calculate the perpendicular projection of the site on the line segment.
49    /// If the projection is outside the line segment, return None.
50    pub fn get_projection(&self, site: &Site) -> Option<Site> {
51        let (x0, y0) = (site.x, site.y);
52        let (x1, y1) = (self.0.x, self.0.y);
53        let (x2, y2) = (self.1.x, self.1.y);
54
55        let a = (x0 - x1, y0 - y1);
56        let b = (x2 - x1, y2 - y1);
57        let dot = a.0 * b.0 + a.1 * b.1;
58        let mag_b2 = b.0 * b.0 + b.1 * b.1;
59        let distance = dot / mag_b2;
60
61        if !(0.0..=1.0).contains(&distance) {
62            return None;
63        }
64        let proj = (x1 + b.0 * distance, y1 + b.1 * distance);
65        Some(Site::new(proj.0, proj.1))
66    }
67
68    /// Calculate the distance from the site to the line segment.
69    pub fn get_distance(&self, site: &Site) -> f64 {
70        let projection = self.get_projection(site);
71        if let Some(projection) = projection {
72            site.distance(&projection)
73        } else {
74            site.distance(&self.0).min(site.distance(&self.1))
75        }
76    }
77}
78
79impl PartialEq for LineSegment {
80    fn eq(&self, other: &Self) -> bool {
81        (self.0 == other.0 && self.1 == other.1) || (self.0 == other.1 && self.1 == other.0)
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn test_get_intersection() {
91        // Parallel lines (no intersection)
92        let line0 = LineSegment::new(Site::new(0.0, 0.0), Site::new(2.0, 2.0));
93        let line1 = LineSegment::new(Site::new(1.0, 1.0), Site::new(3.0, 3.0));
94        assert_eq!(line0.get_intersection(&line1), None);
95
96        // Collinear overlapping lines
97        // This is expected to return None, as the intersection is not a point.
98        let line0 = LineSegment::new(Site::new(1.0, 1.0), Site::new(3.0, 3.0));
99        let line1 = LineSegment::new(Site::new(2.0, 2.0), Site::new(4.0, 4.0));
100        assert_eq!(line0.get_intersection(&line1), None);
101
102        // Intersecting at an end point
103        let line0 = LineSegment::new(Site::new(0.0, 0.0), Site::new(2.0, 0.0));
104        let line1 = LineSegment::new(Site::new(2.0, 0.0), Site::new(2.0, 2.0));
105        assert_eq!(line0.get_intersection(&line1), Some(Site::new(2.0, 0.0)));
106
107        // Vertical and horizontal lines intersecting
108        let line0 = LineSegment::new(Site::new(0.0, 1.0), Site::new(4.0, 1.0));
109        let line1 = LineSegment::new(Site::new(2.0, 0.0), Site::new(2.0, 3.0));
110        assert_eq!(line0.get_intersection(&line1), Some(Site::new(2.0, 1.0)));
111
112        // Collinear lines that barely touch by their edges
113        let line0 = LineSegment::new(Site::new(0.0, 0.0), Site::new(1.0, 1.0));
114        let line1 = LineSegment::new(Site::new(1.0, 1.0), Site::new(2.0, 2.0));
115        assert_eq!(line0.get_intersection(&line1), None);
116
117        // Lines with no intersection (completely separate)
118        let line0 = LineSegment::new(Site::new(0.0, 0.0), Site::new(1.0, 1.0));
119        let line1 = LineSegment::new(Site::new(2.0, 2.0), Site::new(3.0, 3.0));
120        assert_eq!(line0.get_intersection(&line1), None);
121
122        // Edge case: Zero-length line segment
123        // This is expected to return None.
124        let line0 = LineSegment::new(Site::new(1.0, 1.0), Site::new(1.0, 1.0));
125        let line1 = LineSegment::new(Site::new(1.0, 1.0), Site::new(2.0, 2.0));
126        assert_eq!(line0.get_intersection(&line1), None);
127
128        // Intersecting at a point
129        let line0 = LineSegment::new(Site::new(1.0, 3.0), Site::new(3.0, 4.0));
130        let line1 = LineSegment::new(Site::new(1.0, 4.0), Site::new(2.0, 2.0));
131        assert_eq!(line0.get_intersection(&line1), Some(Site::new(1.4, 3.2)));
132    }
133
134    #[test]
135    fn test_get_projection() {
136        let line = LineSegment::new(Site::new(1.0, 1.0), Site::new(3.0, 3.0));
137        let site = Site::new(1.0, 3.0);
138        assert_eq!(line.get_projection(&site), Some(Site::new(2.0, 2.0)));
139
140        let line = LineSegment::new(Site::new(1.0, 1.0), Site::new(2.0, 2.0));
141        let site = Site::new(1.0, 3.0);
142        assert_eq!(line.get_projection(&site), Some(Site::new(2.0, 2.0)));
143
144        let line = LineSegment::new(Site::new(1.0, 1.0), Site::new(1.0, 2.0));
145        let site = Site::new(1.0, 3.0);
146        assert_eq!(line.get_projection(&site), None);
147    }
148}
street_engine/core/geometry/line_segment.rs

street_engine/core/geometry/
line_segment.rs
