line_intersection/
lib.rs

1//! This crate is a tiny utility library for finding the intersection two 2D line segments, rays,
2//! or complete lines. You'll need the `geo` crate to use this crate, because this library uses
3//! `geo`'s data structures.
4//!
5//! To use this library, construct a `LineSegment<T: num_traits::Float>` and `relate` it with
6//! another `LineSegment`. This will return a `LineRelation<T>`, which covers all the possible
7//! relations between those two lines.
8//!
9//! `LineRelation<T>` provides `unique_intersection`, if all you care about is finding a unique
10//! intersection, and (for example) you don't care to distinguish cases where there are zero or an
11//! infinite number of intersections.
12//!
13//! Here's an example of usage:
14//!
15//! ```
16//! extern crate geo;
17//! extern crate line_intersection;
18//!
19//! fn main() {
20//!     // find the intersection of a line segment and an infinite line
21//!     use line_intersection::{LineInterval, LineRelation};
22//!     use geo::{Coordinate, Line, Point};
23//!
24//!     let segment = LineInterval::line_segment(Line {
25//!         start: (0.0, 0.0).into(),
26//!         end: (3.0, 3.0).into(),
27//!     });
28//!
29//!     let line = LineInterval::line(Line {
30//!         start: (2.0, 0.0).into(),
31//!         end: (2.0, 0.1).into(),
32//!     });
33//!
34//!     let intersection = segment.relate(&line).unique_intersection();
35//!     assert_eq!(Some(Point(Coordinate { x: 2.0, y: 2.0 })), intersection);
36//! }
37//! ```
38
39extern crate geo;
40extern crate num_traits;
41
42use geo::{Line, Point};
43use num_traits::Float;
44
45/// An interval (continuous subset) of a line.
46///
47/// `interval_of_intersection` represents what subset of a line this `LineInterval` represents. If
48/// `interval_of_intersection` is `[-Infinity, Infinity]`, then it's a line going through
49/// `line.start` and `line.end`; if it's `[0, Infinity]` it's a ray, starting at `line.start`
50/// extending infinitely in the direction of `line.end` and beyond; if it's `[0, 1]`, it's a line
51/// segment from `line.from` to `line.end`.
52///
53/// It should always be the case that `interval_of_intersection.0 < interval_of_intersection.1`,
54/// unless you want a degenerate line that cannot be intersected.
55#[derive(Debug, PartialEq)]
56pub struct LineInterval<T: Float> {
57    pub line: Line<T>,
58    pub interval_of_intersection: (T, T),
59}
60
61/// The relationship between two line segments.
62#[derive(Debug, PartialEq)]
63pub enum LineRelation<T: Float> {
64    /// The line intervals are not parallel (or anti-parallel), and "meet" each other at exactly
65    /// one point.
66    DivergentIntersecting(Point<T>),
67    /// The line intervals are not parallel (or anti-parallel), and do not intersect; they "miss"
68    /// each other.
69    DivergentDisjoint,
70    /// The line intervals lie on the same line. They may or may not overlap, and this intersection
71    /// is possibly infinite.
72    Collinear,
73    /// The line intervals are parallel or anti-parallel.
74    Parallel,
75}
76
77impl<T: Float> LineRelation<T> {
78    pub fn unique_intersection(self) -> Option<Point<T>> {
79        match self {
80            LineRelation::DivergentIntersecting(p) => Some(p),
81            _ => None,
82        }
83    }
84}
85
86impl<T: Float> LineInterval<T> {
87    pub fn line_segment(line: Line<T>) -> LineInterval<T> {
88        LineInterval {
89            line: line,
90            interval_of_intersection: (T::zero(), T::one()),
91        }
92    }
93
94    pub fn ray(line: Line<T>) -> LineInterval<T> {
95        LineInterval {
96            line: line,
97            interval_of_intersection: (T::zero(), T::infinity()),
98        }
99    }
100
101    pub fn line(line: Line<T>) -> LineInterval<T> {
102        LineInterval {
103            line: line,
104            interval_of_intersection: (T::neg_infinity(), T::infinity()),
105        }
106    }
107
108    /// Get the relationship between this line segment and another.
109    pub fn relate(&self, other: &LineInterval<T>) -> LineRelation<T> {
110        // see https://stackoverflow.com/a/565282
111        let p = self.line.start;
112        let q = other.line.start;
113        let r = self.line.end - self.line.start;
114        let s = other.line.end - other.line.start;
115
116        let r_cross_s = Self::cross(&r, &s);
117        let q_minus_p = q - p;
118        let q_minus_p_cross_r = Self::cross(&q_minus_p, &r);
119
120        // are the lines are parallel?
121        if r_cross_s == T::zero() {
122            // are the lines collinear?
123            if q_minus_p_cross_r == T::zero() {
124                // the lines are collinear
125                LineRelation::Collinear
126            } else {
127                // the lines are parallel but not collinear
128                LineRelation::Parallel
129            }
130        } else {
131            // the lines are not parallel
132            let t = Self::cross(&q_minus_p, &Self::div(&s, r_cross_s));
133            let u = Self::cross(&q_minus_p, &Self::div(&r, r_cross_s));
134
135            // are the intersection coordinates both in range?
136            let t_in_range = self.interval_of_intersection.0 <= t &&
137                t <= self.interval_of_intersection.1;
138            let u_in_range = other.interval_of_intersection.0 <= u &&
139                u <= other.interval_of_intersection.1;
140
141            if t_in_range && u_in_range {
142                // there is an intersection
143                LineRelation::DivergentIntersecting(Self::t_coord_to_point(&p, &r, t))
144            } else {
145                // there is no intersection
146                LineRelation::DivergentDisjoint
147            }
148        }
149    }
150
151    fn cross(a: &Point<T>, b: &Point<T>) -> T {
152        a.x() * b.y() - a.y() * b.x()
153    }
154
155    fn div(a: &Point<T>, b: T) -> Point<T> {
156        (a.x() / b, a.y() / b).into()
157    }
158
159    fn t_coord_to_point(p: &Point<T>, r: &Point<T>, t: T) -> Point<T> {
160        (p.x() + t * r.x(), p.y() + t * r.y()).into()
161    }
162}
163
164#[cfg(test)]
165mod tests {
166    use super::*;
167
168    #[test]
169    fn divergent_intersecting_segments() {
170        let a = Line {
171            start: (1.0, 0.0).into(),
172            end: (1.0, 1.0).into(),
173        };
174        let b = Line {
175            start: (0.0, 0.0).into(),
176            end: (2.0, 0.5).into(),
177        };
178        let s1 = LineInterval::line_segment(a);
179        let s2 = LineInterval::line_segment(b);
180        let relation = LineRelation::DivergentIntersecting((1.0, 0.25).into());
181
182        assert_eq!(relation, s1.relate(&s2));
183        assert_eq!(relation, s2.relate(&s1));
184    }
185
186    #[test]
187    fn divergent_intersecting_segment_and_ray() {
188        let a = Line {
189            start: (0.0, 0.0).into(),
190            end: (1.0, 1.0).into(),
191        };
192        let b = Line {
193            start: (2.0, 0.0).into(),
194            end: (2.0, 3.0).into(),
195        };
196        let s1 = LineInterval::ray(a);
197        let s2 = LineInterval::line_segment(b);
198        let relation = LineRelation::DivergentIntersecting((2.0, 2.0).into());
199
200        assert_eq!(relation, s1.relate(&s2));
201        assert_eq!(relation, s2.relate(&s1));
202    }
203
204    #[test]
205    fn divergent_disjoint_segments() {
206        let a = Line {
207            start: (0.0, 0.0).into(),
208            end: (1.0, 1.0).into(),
209        };
210        let b = Line {
211            start: (3.0, 0.0).into(),
212            end: (0.0, 3.0).into(),
213        };
214        let s1 = LineInterval::line_segment(a);
215        let s2 = LineInterval::line_segment(b);
216        let relation = LineRelation::DivergentDisjoint;
217
218        assert_eq!(relation, s1.relate(&s2));
219        assert_eq!(relation, s2.relate(&s1));
220    }
221
222    #[test]
223    fn divergent_disjoint_ray_and_line() {
224        let a = Line {
225            start: (1.0, 1.0).into(),
226            end: (0.0, 0.0).into(),
227        };
228        let b = Line {
229            start: (3.0, 0.0).into(),
230            end: (0.0, 3.0).into(),
231        };
232        let s1 = LineInterval::ray(a);
233        let s2 = LineInterval::line(b);
234        let relation = LineRelation::DivergentDisjoint;
235
236        assert_eq!(relation, s1.relate(&s2));
237        assert_eq!(relation, s2.relate(&s1));
238    }
239
240    #[test]
241    fn parallel_disjoint_segments() {
242        let a = Line {
243            start: (0.0, 0.0).into(),
244            end: (1.0, 1.0).into(),
245        };
246        let b = Line {
247            start: (0.0, 1.0).into(),
248            end: (1.0, 2.0).into(),
249        };
250        let s1 = LineInterval::line(a);
251        let s2 = LineInterval::line(b);
252        let relation = LineRelation::Parallel;
253
254        assert_eq!(relation, s1.relate(&s2));
255        assert_eq!(relation, s2.relate(&s1));
256    }
257
258    #[test]
259    fn collinear_overlapping_segment_and_line() {
260        let a = Line {
261            start: (0.0, 0.0).into(),
262            end: (0.0, 1.5).into(),
263        };
264        let b = Line {
265            start: (0.0, 4.0).into(),
266            end: (0.0, 5.0).into(),
267        };
268        let s1 = LineInterval::line(a);
269        let s2 = LineInterval::ray(b);
270        let relation = LineRelation::Collinear;
271
272        assert_eq!(relation, s1.relate(&s2));
273        assert_eq!(relation, s2.relate(&s1));
274    }
275}
line_intersection/lib.rs

line_intersection/
lib.rs
