lyon_geom/
line.rs

1use crate::scalar::Scalar;
2use crate::segment::Segment;
3use crate::traits::Transformation;
4use crate::utils::min_max;
5use crate::{point, vector, Box2D, Point, Vector};
6use core::mem::swap;
7
8use core::ops::Range;
9
10/// A linear segment.
11#[derive(Copy, Clone, Debug, PartialEq)]
12#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
13pub struct LineSegment<S> {
14    pub from: Point<S>,
15    pub to: Point<S>,
16}
17
18impl<S: Scalar> LineSegment<S> {
19    /// Sample the segment at t (expecting t between 0 and 1).
20    #[inline]
21    pub fn sample(&self, t: S) -> Point<S> {
22        self.from.lerp(self.to, t)
23    }
24
25    /// Sample the x coordinate of the segment at t (expecting t between 0 and 1).
26    #[inline]
27    pub fn x(&self, t: S) -> S {
28        self.from.x * (S::ONE - t) + self.to.x * t
29    }
30
31    /// Sample the y coordinate of the segment at t (expecting t between 0 and 1).
32    #[inline]
33    pub fn y(&self, t: S) -> S {
34        self.from.y * (S::ONE - t) + self.to.y * t
35    }
36
37    #[inline]
38    pub fn from(&self) -> Point<S> {
39        self.from
40    }
41
42    #[inline]
43    pub fn to(&self) -> Point<S> {
44        self.to
45    }
46
47    pub fn solve_t_for_x(&self, x: S) -> S {
48        let dx = self.to.x - self.from.x;
49        if dx == S::ZERO {
50            return S::ZERO;
51        }
52
53        (x - self.from.x) / dx
54    }
55
56    pub fn solve_t_for_y(&self, y: S) -> S {
57        let dy = self.to.y - self.from.y;
58        if dy == S::ZERO {
59            return S::ZERO;
60        }
61
62        (y - self.from.y) / dy
63    }
64
65    pub fn solve_y_for_x(&self, x: S) -> S {
66        self.y(self.solve_t_for_x(x))
67    }
68
69    pub fn solve_x_for_y(&self, y: S) -> S {
70        self.x(self.solve_t_for_y(y))
71    }
72
73    /// Returns an inverted version of this segment where the beginning and the end
74    /// points are swapped.
75    #[inline]
76    pub fn flip(&self) -> Self {
77        LineSegment {
78            from: self.to,
79            to: self.from,
80        }
81    }
82
83    /// Return the sub-segment inside a given range of t.
84    ///
85    /// This is equivalent splitting at the range's end points.
86    pub fn split_range(&self, t_range: Range<S>) -> Self {
87        LineSegment {
88            from: self.from.lerp(self.to, t_range.start),
89            to: self.from.lerp(self.to, t_range.end),
90        }
91    }
92
93    /// Split this curve into two sub-segments.
94    #[inline]
95    pub fn split(&self, t: S) -> (Self, Self) {
96        let split_point = self.sample(t);
97
98        (
99            LineSegment {
100                from: self.from,
101                to: split_point,
102            },
103            LineSegment {
104                from: split_point,
105                to: self.to,
106            },
107        )
108    }
109
110    /// Return the segment before the split point.
111    #[inline]
112    pub fn before_split(&self, t: S) -> Self {
113        LineSegment {
114            from: self.from,
115            to: self.sample(t),
116        }
117    }
118
119    /// Return the segment after the split point.
120    #[inline]
121    pub fn after_split(&self, t: S) -> Self {
122        LineSegment {
123            from: self.sample(t),
124            to: self.to,
125        }
126    }
127
128    pub fn split_at_x(&self, x: S) -> (Self, Self) {
129        self.split(self.solve_t_for_x(x))
130    }
131
132    /// Return the smallest rectangle containing this segment.
133    #[inline]
134    pub fn bounding_box(&self) -> Box2D<S> {
135        let (min_x, max_x) = self.bounding_range_x();
136        let (min_y, max_y) = self.bounding_range_y();
137
138        Box2D {
139            min: point(min_x, min_y),
140            max: point(max_x, max_y),
141        }
142    }
143
144    // TODO: Make these two public?
145    #[inline]
146    pub(crate) fn bounding_range_x(&self) -> (S, S) {
147        min_max(self.from.x, self.to.x)
148    }
149
150    #[inline]
151    pub(crate) fn bounding_range_y(&self) -> (S, S) {
152        min_max(self.from.y, self.to.y)
153    }
154
155    /// Returns the vector between this segment's `from` and `to` points.
156    #[inline]
157    pub fn to_vector(&self) -> Vector<S> {
158        self.to - self.from
159    }
160
161    /// Returns the line containing this segment.
162    #[inline]
163    pub fn to_line(&self) -> Line<S> {
164        Line {
165            point: self.from,
166            vector: self.to - self.from,
167        }
168    }
169
170    /// Computes the length of this segment.
171    #[inline]
172    pub fn length(&self) -> S {
173        self.to_vector().length()
174    }
175
176    /// Computes the squared length of this segment.
177    #[inline]
178    pub fn square_length(&self) -> S {
179        self.to_vector().square_length()
180    }
181
182    /// Changes the segment's length, moving destination point.
183    pub fn set_length(&mut self, new_length: S) {
184        let v = self.to_vector();
185        let old_length = v.length();
186        self.to = self.from + v * (new_length / old_length);
187    }
188
189    /// Computes third mid-point of this segment.
190    pub fn mid_point(&mut self) -> Point<S> {
191        (self.from + self.to.to_vector()) / S::TWO
192    }
193
194    #[inline]
195    pub fn translate(&mut self, by: Vector<S>) -> Self {
196        LineSegment {
197            from: self.from + by,
198            to: self.to + by,
199        }
200    }
201
202    /// Applies the transform to this segment and returns the results.
203    #[inline]
204    pub fn transformed<T: Transformation<S>>(&self, transform: &T) -> Self {
205        LineSegment {
206            from: transform.transform_point(self.from),
207            to: transform.transform_point(self.to),
208        }
209    }
210
211    /// Computes the intersection (if any) between this segment and another one.
212    ///
213    /// The result is provided in the form of the `t` parameter of each
214    /// segment. To get the intersection point, sample one of the segments
215    /// at the corresponding value.
216    #[allow(clippy::suspicious_operation_groupings)]
217    pub fn intersection_t(&self, other: &Self) -> Option<(S, S)> {
218        if self.to == other.to
219            || self.from == other.from
220            || self.from == other.to
221            || self.to == other.from
222        {
223            return None;
224        }
225
226        let v1 = self.to_vector();
227        let v2 = other.to_vector();
228
229        let v1_cross_v2 = v1.cross(v2);
230
231        if v1_cross_v2 == S::ZERO {
232            // The segments are parallel
233            return None;
234        }
235
236        let sign_v1_cross_v2 = S::signum(v1_cross_v2);
237        let abs_v1_cross_v2 = S::abs(v1_cross_v2);
238
239        let v3 = other.from - self.from;
240
241        // t and u should be divided by v1_cross_v2, but we postpone that to not lose precision.
242        // We have to respect the sign of v1_cross_v2 (and therefore t and u) so we apply it now and
243        // will use the absolute value of v1_cross_v2 afterwards.
244        let t = v3.cross(v2) * sign_v1_cross_v2;
245        let u = v3.cross(v1) * sign_v1_cross_v2;
246
247        if t < S::ZERO || t > abs_v1_cross_v2 || u < S::ZERO || u > abs_v1_cross_v2 {
248            return None;
249        }
250
251        Some((t / abs_v1_cross_v2, u / abs_v1_cross_v2))
252    }
253
254    #[inline]
255    pub fn intersection(&self, other: &Self) -> Option<Point<S>> {
256        self.intersection_t(other).map(|(t, _)| self.sample(t))
257    }
258
259    pub fn line_intersection_t(&self, line: &Line<S>) -> Option<S> {
260        let v1 = self.to_vector();
261        let v2 = line.vector;
262
263        let v1_cross_v2 = v1.cross(v2);
264
265        if v1_cross_v2 == S::ZERO {
266            // The segments are parallel
267            return None;
268        }
269
270        let sign_v1_cross_v2 = S::signum(v1_cross_v2);
271        let abs_v1_cross_v2 = S::abs(v1_cross_v2);
272
273        let v3 = line.point - self.from;
274        let t = v3.cross(v2) * sign_v1_cross_v2;
275
276        if t < S::ZERO || t > abs_v1_cross_v2 {
277            return None;
278        }
279
280        Some(t / abs_v1_cross_v2)
281    }
282
283    #[inline]
284    pub fn line_intersection(&self, line: &Line<S>) -> Option<Point<S>> {
285        self.line_intersection_t(line).map(|t| self.sample(t))
286    }
287
288    // TODO: Consider only intersecting in the [0, 1[ range instead of [0, 1]
289    pub fn horizontal_line_intersection_t(&self, y: S) -> Option<S> {
290        Self::axis_aligned_intersection_1d(self.from.y, self.to.y, y)
291    }
292
293    pub fn vertical_line_intersection_t(&self, x: S) -> Option<S> {
294        Self::axis_aligned_intersection_1d(self.from.x, self.to.x, x)
295    }
296
297    #[inline]
298    pub fn horizontal_line_intersection(&self, y: S) -> Option<Point<S>> {
299        self.horizontal_line_intersection_t(y)
300            .map(|t| self.sample(t))
301    }
302
303    #[inline]
304    pub fn vertical_line_intersection(&self, x: S) -> Option<Point<S>> {
305        self.vertical_line_intersection_t(x).map(|t| self.sample(t))
306    }
307
308    fn axis_aligned_intersection_1d(mut a: S, mut b: S, v: S) -> Option<S> {
309        // TODO: is it really useful to swap?
310        let swap = a > b;
311        if swap {
312            core::mem::swap(&mut a, &mut b);
313        }
314
315        let d = b - a;
316        if d == S::ZERO {
317            return None;
318        }
319
320        let t = (v - a) / d;
321
322        if t < S::ZERO || t > S::ONE {
323            return None;
324        }
325
326        Some(if swap { S::ONE - t } else { t })
327    }
328
329    #[inline]
330    pub fn intersects(&self, other: &Self) -> bool {
331        self.intersection_t(other).is_some()
332    }
333
334    #[inline]
335    pub fn intersects_line(&self, line: &Line<S>) -> bool {
336        self.line_intersection_t(line).is_some()
337    }
338
339    pub fn overlaps_line(&self, line: &Line<S>) -> bool {
340        let v1 = self.to_vector();
341        let v2 = line.vector;
342        let v3 = line.point - self.from;
343
344        v1.cross(v2) == S::ZERO && v1.cross(v3) == S::ZERO
345    }
346
347    pub fn overlaps_segment(&self, other: &LineSegment<S>) -> bool {
348        if !self.overlaps_line(&other.to_line()) {
349            return false;
350        }
351
352        let v1 = self.to - self.from;
353        let v2 = other.from - self.from;
354        let v3 = other.to - self.from;
355        let mut a = S::ZERO;
356        let mut b = v1.dot(v1);
357        let mut c = v1.dot(v2);
358        let mut d = v1.dot(v3);
359
360        if a > b {
361            swap(&mut a, &mut b);
362        }
363        if c > d {
364            swap(&mut d, &mut c);
365        }
366
367        (c > a && c < b)
368            || (d > a && d < b)
369            || (a > c && a < d)
370            || (b > c && b < d)
371            || (a == c && b == d)
372    }
373
374    pub fn contains_segment(&self, other: &LineSegment<S>) -> bool {
375        if !self.overlaps_line(&other.to_line()) {
376            return false;
377        }
378
379        let v1 = self.to - self.from;
380        let v2 = other.from - self.from;
381        let v3 = other.to - self.from;
382        let mut a = S::ZERO;
383        let mut b = v1.dot(v1);
384        let mut c = v1.dot(v2);
385        let mut d = v1.dot(v3);
386
387        if a > b {
388            swap(&mut a, &mut b);
389        }
390        if c > d {
391            swap(&mut d, &mut c);
392        }
393
394        c >= a && c <= b && d >= a && d <= b
395    }
396
397    /// Horizontally clip this segment against a range of the x axis.
398    pub fn clipped_x(&self, clip: Range<S>) -> Option<Self> {
399        if (self.from.x < clip.start && self.to.x < clip.start)
400            || (self.from.x > clip.end && self.to.x > clip.end)
401        {
402            return None;
403        }
404
405        let mut flipped = false;
406        let mut result = *self;
407
408        if result.from.x > result.to.x {
409            flipped = true;
410            result = result.flip();
411        }
412
413        if result.from.x >= clip.start && result.to.x <= clip.end {
414            return Some(*self);
415        }
416
417        if result.from.x < clip.start {
418            let t = result
419                .vertical_line_intersection_t(clip.start)
420                .unwrap_or(S::ZERO);
421            result.from.x = clip.start;
422            result.from.y = result.y(t);
423        }
424
425        if result.to.x > clip.end {
426            let t = result
427                .vertical_line_intersection_t(clip.end)
428                .unwrap_or(S::ZERO);
429            result.to.x = clip.end;
430            result.to.y = result.y(t);
431        }
432
433        if flipped {
434            result = result.flip();
435        }
436
437        Some(result)
438    }
439
440    /// Vertically clip this segment against a range of the y axis.
441    pub fn clipped_y(&self, clip: Range<S>) -> Option<Self> {
442        fn transpose<S: Copy>(r: &LineSegment<S>) -> LineSegment<S> {
443            LineSegment {
444                from: r.from.yx(),
445                to: r.to.yx(),
446            }
447        }
448
449        Some(transpose(&transpose(self).clipped_x(clip)?))
450    }
451
452    /// Clip this segment against a rectangle.
453    pub fn clipped(&self, clip: &Box2D<S>) -> Option<Self> {
454        self.clipped_x(clip.x_range())?.clipped_y(clip.y_range())
455    }
456
457    /// Computes the distance between this segment and a point.
458    #[inline]
459    pub fn distance_to_point(&self, p: Point<S>) -> S {
460        self.square_distance_to_point(p).sqrt()
461    }
462
463    /// Computes the squared distance between this segment and a point.
464    ///
465    /// Can be useful to save a square root and a division when comparing against
466    /// a distance that can be squared.
467    #[inline]
468    pub fn square_distance_to_point(&self, p: Point<S>) -> S {
469        (self.closest_point(p) - p).square_length()
470    }
471
472    /// Computes the closest point on this segment to `p`.
473    #[inline]
474    pub fn closest_point(&self, p: Point<S>) -> Point<S> {
475        let v1 = self.to - self.from;
476        let v2 = p - self.from;
477        let t = S::min(S::max(v2.dot(v1) / v1.dot(v1), S::ZERO), S::ONE);
478
479        self.from + v1 * t
480    }
481
482    #[inline]
483    pub fn to_f32(&self) -> LineSegment<f32> {
484        LineSegment {
485            from: self.from.to_f32(),
486            to: self.to.to_f32(),
487        }
488    }
489
490    #[inline]
491    pub fn to_f64(&self) -> LineSegment<f64> {
492        LineSegment {
493            from: self.from.to_f64(),
494            to: self.to.to_f64(),
495        }
496    }
497}
498
499impl<S: Scalar> Segment for LineSegment<S> {
500    type Scalar = S;
501    fn from(&self) -> Point<S> {
502        self.from
503    }
504    fn to(&self) -> Point<S> {
505        self.to
506    }
507    fn sample(&self, t: S) -> Point<S> {
508        self.sample(t)
509    }
510    fn x(&self, t: S) -> S {
511        self.x(t)
512    }
513    fn y(&self, t: S) -> S {
514        self.y(t)
515    }
516    fn derivative(&self, _t: S) -> Vector<S> {
517        self.to_vector()
518    }
519    fn dx(&self, _t: S) -> S {
520        self.to.x - self.from.x
521    }
522    fn dy(&self, _t: S) -> S {
523        self.to.y - self.from.y
524    }
525    fn split(&self, t: S) -> (Self, Self) {
526        self.split(t)
527    }
528    fn before_split(&self, t: S) -> Self {
529        self.before_split(t)
530    }
531    fn after_split(&self, t: S) -> Self {
532        self.after_split(t)
533    }
534    fn split_range(&self, t_range: Range<S>) -> Self {
535        self.split_range(t_range)
536    }
537    fn flip(&self) -> Self {
538        self.flip()
539    }
540    fn approximate_length(&self, _tolerance: S) -> S {
541        self.length()
542    }
543
544    fn for_each_flattened_with_t(
545        &self,
546        _tolerance: Self::Scalar,
547        callback: &mut dyn FnMut(&LineSegment<S>, Range<S>),
548    ) {
549        callback(self, S::ZERO..S::ONE);
550    }
551}
552
553/// An infinite line defined by a point and a vector.
554#[derive(Copy, Clone, Debug)]
555#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
556pub struct Line<S> {
557    pub point: Point<S>,
558    pub vector: Vector<S>,
559}
560
561impl<S: Scalar> Line<S> {
562    pub fn intersection(&self, other: &Self) -> Option<Point<S>> {
563        let det = self.vector.cross(other.vector);
564        if S::abs(det) <= S::EPSILON {
565            // The lines are very close to parallel
566            return None;
567        }
568        let inv_det = S::ONE / det;
569        let self_p2 = self.point + self.vector;
570        let other_p2 = other.point + other.vector;
571        let a = self.point.to_vector().cross(self_p2.to_vector());
572        let b = other.point.to_vector().cross(other_p2.to_vector());
573
574        Some(point(
575            (b * self.vector.x - a * other.vector.x) * inv_det,
576            (b * self.vector.y - a * other.vector.y) * inv_det,
577        ))
578    }
579
580    pub fn distance_to_point(&self, p: &Point<S>) -> S {
581        S::abs(self.signed_distance_to_point(p))
582    }
583
584    pub fn signed_distance_to_point(&self, p: &Point<S>) -> S {
585        let v = *p - self.point;
586        self.vector.cross(v) / self.vector.length()
587    }
588
589    /// Returned the squared distance to a point.
590    ///
591    /// Can be useful to avoid a square root when comparing against a
592    /// distance that can be squared instead.
593    pub fn square_distance_to_point(&self, p: Point<S>) -> S {
594        let v = p - self.point;
595        let c = self.vector.cross(v);
596        (c * c) / self.vector.square_length()
597    }
598
599    pub fn equation(&self) -> LineEquation<S> {
600        let a = -self.vector.y;
601        let b = self.vector.x;
602        let c = -(a * self.point.x + b * self.point.y);
603
604        LineEquation::new(a, b, c)
605    }
606
607    pub fn intersects_box(&self, rect: &Box2D<S>) -> bool {
608        let v = self.vector;
609
610        let diagonal = if (v.y >= S::ZERO) ^ (v.x >= S::ZERO) {
611            LineSegment {
612                from: rect.min,
613                to: rect.max,
614            }
615        } else {
616            LineSegment {
617                from: point(rect.max.x, rect.min.y),
618                to: point(rect.min.x, rect.max.y),
619            }
620        };
621
622        diagonal.intersects_line(self)
623    }
624
625    #[inline]
626    pub fn to_f32(&self) -> Line<f32> {
627        Line {
628            point: self.point.to_f32(),
629            vector: self.vector.to_f32(),
630        }
631    }
632
633    #[inline]
634    pub fn to_f64(&self) -> Line<f64> {
635        Line {
636            point: self.point.to_f64(),
637            vector: self.vector.to_f64(),
638        }
639    }
640}
641
642/// A line defined by the equation
643/// `a * x + b * y + c = 0; a * a + b * b = 1`.
644#[derive(Copy, Clone, Debug, PartialEq, Eq)]
645#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
646pub struct LineEquation<S> {
647    a: S,
648    b: S,
649    c: S,
650}
651
652impl<S: Scalar> LineEquation<S> {
653    pub fn new(a: S, b: S, c: S) -> Self {
654        debug_assert!(a != S::ZERO || b != S::ZERO);
655        let div = S::ONE / S::sqrt(a * a + b * b);
656        LineEquation {
657            a: a * div,
658            b: b * div,
659            c: c * div,
660        }
661    }
662
663    #[inline]
664    pub fn a(&self) -> S {
665        self.a
666    }
667
668    #[inline]
669    pub fn b(&self) -> S {
670        self.b
671    }
672
673    #[inline]
674    pub fn c(&self) -> S {
675        self.c
676    }
677
678    pub fn project_point(&self, p: &Point<S>) -> Point<S> {
679        point(
680            self.b * (self.b * p.x - self.a * p.y) - self.a * self.c,
681            self.a * (self.a * p.y - self.b * p.x) - self.b * self.c,
682        )
683    }
684
685    #[inline]
686    pub fn signed_distance_to_point(&self, p: &Point<S>) -> S {
687        self.a * p.x + self.b * p.y + self.c
688    }
689
690    #[inline]
691    pub fn distance_to_point(&self, p: &Point<S>) -> S {
692        S::abs(self.signed_distance_to_point(p))
693    }
694
695    #[inline]
696    pub fn invert(&self) -> Self {
697        LineEquation {
698            a: -self.a,
699            b: -self.b,
700            c: -self.c,
701        }
702    }
703
704    #[inline]
705    pub fn parallel_line(&self, p: &Point<S>) -> Self {
706        let c = -(self.a * p.x + self.b * p.y);
707        LineEquation {
708            a: self.a,
709            b: self.b,
710            c,
711        }
712    }
713
714    #[inline]
715    pub fn offset(&self, d: S) -> Self {
716        LineEquation {
717            a: self.a,
718            b: self.b,
719            c: self.c - d,
720        }
721    }
722
723    #[inline]
724    pub fn tangent(&self) -> Vector<S> {
725        vector(self.b, -self.a)
726    }
727
728    #[inline]
729    pub fn normal(&self) -> Vector<S> {
730        vector(self.a, self.b)
731    }
732
733    #[inline]
734    pub fn solve_y_for_x(&self, x: S) -> Option<S> {
735        if self.b == S::ZERO {
736            return None;
737        }
738
739        Some((self.a * x + self.c) / -self.b)
740    }
741
742    #[inline]
743    pub fn solve_x_for_y(&self, y: S) -> Option<S> {
744        if self.a == S::ZERO {
745            return None;
746        }
747
748        Some((self.b * y + self.c) / -self.a)
749    }
750
751    #[inline]
752    pub fn is_horizontal(&self) -> bool {
753        self.a == S::ZERO
754    }
755
756    #[inline]
757    pub fn is_vertical(&self) -> bool {
758        self.b == S::ZERO
759    }
760}
761
762#[cfg(test)]
763fn fuzzy_eq_f32(a: f32, b: f32, epsilon: f32) -> bool {
764    f32::abs(a - b) <= epsilon
765}
766
767#[cfg(test)]
768fn fuzzy_eq_vector(a: Vector<f32>, b: Vector<f32>, epsilon: f32) -> bool {
769    fuzzy_eq_f32(a.x, b.x, epsilon) && fuzzy_eq_f32(a.y, b.y, epsilon)
770}
771
772#[cfg(test)]
773fn fuzzy_eq_point(a: Point<f32>, b: Point<f32>, epsilon: f32) -> bool {
774    fuzzy_eq_vector(a.to_vector(), b.to_vector(), epsilon)
775}
776
777#[test]
778fn intersection_rotated() {
779    use core::f32::consts::PI;
780    let epsilon = 0.0001;
781    let count: u32 = 100;
782
783    for i in 0..count {
784        for j in 0..count {
785            if i % (count / 2) == j % (count / 2) {
786                // avoid the colinear case.
787                continue;
788            }
789
790            let angle1 = i as f32 / (count as f32) * 2.0 * PI;
791            let angle2 = j as f32 / (count as f32) * 2.0 * PI;
792
793            let l1 = LineSegment {
794                from: point(10.0 * angle1.cos(), 10.0 * angle1.sin()),
795                to: point(-10.0 * angle1.cos(), -10.0 * angle1.sin()),
796            };
797
798            let l2 = LineSegment {
799                from: point(10.0 * angle2.cos(), 10.0 * angle2.sin()),
800                to: point(-10.0 * angle2.cos(), -10.0 * angle2.sin()),
801            };
802
803            assert!(l1.intersects(&l2));
804
805            assert!(fuzzy_eq_point(
806                l1.sample(l1.intersection_t(&l2).unwrap().0),
807                point(0.0, 0.0),
808                epsilon
809            ));
810
811            assert!(fuzzy_eq_point(
812                l2.sample(l1.intersection_t(&l2).unwrap().1),
813                point(0.0, 0.0),
814                epsilon
815            ));
816        }
817    }
818}
819
820#[test]
821fn intersection_touching() {
822    let l1 = LineSegment {
823        from: point(0.0, 0.0),
824        to: point(10.0, 10.0),
825    };
826
827    let l2 = LineSegment {
828        from: point(10.0, 10.0),
829        to: point(10.0, 0.0),
830    };
831
832    assert!(!l1.intersects(&l2));
833    assert!(l1.intersection(&l2).is_none());
834}
835
836#[test]
837fn intersection_overlap() {
838    // It's hard to define the intersection points of two segments that overlap,
839    // (would be a region rather than a point) and more importantly, in practice
840    // the algorithms in lyon don't need to consider this special case as an intersection,
841    // so we choose to treat overlapping segments as not intersecting.
842
843    let l1 = LineSegment {
844        from: point(0.0, 0.0),
845        to: point(10.0, 0.0),
846    };
847
848    let l2 = LineSegment {
849        from: point(5.0, 00.0),
850        to: point(15.0, 0.0),
851    };
852
853    assert!(!l1.intersects(&l2));
854    assert!(l1.intersection(&l2).is_none());
855}
856
857#[cfg(test)]
858use euclid::approxeq::ApproxEq;
859
860#[test]
861fn bounding_box() {
862    let l1 = LineSegment {
863        from: point(1.0, 5.0),
864        to: point(5.0, 7.0),
865    };
866    let r1 = Box2D {
867        min: point(1.0, 5.0),
868        max: point(5.0, 7.0),
869    };
870
871    let l2 = LineSegment {
872        from: point(5.0, 5.0),
873        to: point(1.0, 1.0),
874    };
875    let r2 = Box2D {
876        min: point(1.0, 1.0),
877        max: point(5.0, 5.0),
878    };
879
880    let l3 = LineSegment {
881        from: point(3.0, 3.0),
882        to: point(1.0, 5.0),
883    };
884    let r3 = Box2D {
885        min: point(1.0, 3.0),
886        max: point(3.0, 5.0),
887    };
888
889    let cases = std::vec![(l1, r1), (l2, r2), (l3, r3)];
890    for &(ls, r) in &cases {
891        assert_eq!(ls.bounding_box(), r);
892    }
893}
894
895#[test]
896fn distance_to_point() {
897    use crate::vector;
898
899    let l1 = Line {
900        point: point(2.0f32, 3.0),
901        vector: vector(-1.5, 0.0),
902    };
903
904    let l2 = Line {
905        point: point(3.0f32, 3.0),
906        vector: vector(1.5, 1.5),
907    };
908
909    assert!(l1
910        .signed_distance_to_point(&point(1.1, 4.0))
911        .approx_eq(&-1.0));
912    assert!(l1
913        .signed_distance_to_point(&point(2.3, 2.0))
914        .approx_eq(&1.0));
915
916    assert!(l2
917        .signed_distance_to_point(&point(1.0, 0.0))
918        .approx_eq(&(-f32::sqrt(2.0) / 2.0)));
919    assert!(l2
920        .signed_distance_to_point(&point(0.0, 1.0))
921        .approx_eq(&(f32::sqrt(2.0) / 2.0)));
922
923    assert!(l1
924        .equation()
925        .distance_to_point(&point(1.1, 4.0))
926        .approx_eq(&1.0));
927    assert!(l1
928        .equation()
929        .distance_to_point(&point(2.3, 2.0))
930        .approx_eq(&1.0));
931    assert!(l2
932        .equation()
933        .distance_to_point(&point(1.0, 0.0))
934        .approx_eq(&(f32::sqrt(2.0) / 2.0)));
935    assert!(l2
936        .equation()
937        .distance_to_point(&point(0.0, 1.0))
938        .approx_eq(&(f32::sqrt(2.0) / 2.0)));
939
940    assert!(l1
941        .equation()
942        .signed_distance_to_point(&point(1.1, 4.0))
943        .approx_eq(&l1.signed_distance_to_point(&point(1.1, 4.0))));
944    assert!(l1
945        .equation()
946        .signed_distance_to_point(&point(2.3, 2.0))
947        .approx_eq(&l1.signed_distance_to_point(&point(2.3, 2.0))));
948
949    assert!(l2
950        .equation()
951        .signed_distance_to_point(&point(1.0, 0.0))
952        .approx_eq(&l2.signed_distance_to_point(&point(1.0, 0.0))));
953    assert!(l2
954        .equation()
955        .signed_distance_to_point(&point(0.0, 1.0))
956        .approx_eq(&l2.signed_distance_to_point(&point(0.0, 1.0))));
957}
958
959#[test]
960fn solve_y_for_x() {
961    let line = Line {
962        point: Point::new(1.0, 1.0),
963        vector: Vector::new(2.0, 4.0),
964    };
965    let eqn = line.equation();
966
967    if let Some(y) = eqn.solve_y_for_x(line.point.x) {
968        std::println!("{y:?} != {:?}", line.point.y);
969        assert!(f64::abs(y - line.point.y) < 0.000001)
970    }
971
972    if let Some(x) = eqn.solve_x_for_y(line.point.y) {
973        assert!(f64::abs(x - line.point.x) < 0.000001)
974    }
975
976    let mut angle = 0.1;
977    for _ in 0..100 {
978        let (sin, cos) = f64::sin_cos(angle);
979        let line = Line {
980            point: Point::new(-1000.0, 600.0),
981            vector: Vector::new(cos * 100.0, sin * 100.0),
982        };
983        let eqn = line.equation();
984
985        if let Some(y) = eqn.solve_y_for_x(line.point.x) {
986            std::println!("{y:?} != {:?}", line.point.y);
987            assert!(f64::abs(y - line.point.y) < 0.000001)
988        }
989
990        if let Some(x) = eqn.solve_x_for_y(line.point.y) {
991            assert!(f64::abs(x - line.point.x) < 0.000001)
992        }
993
994        angle += 0.001;
995    }
996}
997
998#[test]
999fn offset() {
1000    let l1 = LineEquation::new(2.0, 3.0, 1.0);
1001    let p = Point::new(10.0, 3.0);
1002    let d = l1.signed_distance_to_point(&p);
1003    let l2 = l1.offset(d);
1004    assert!(l2.distance_to_point(&p) < 0.0000001f64);
1005}
1006
1007#[test]
1008fn set_length() {
1009    let mut a = LineSegment {
1010        from: point(10.0, 1.0),
1011        to: point(100.0, -15.0),
1012    };
1013    a.set_length(1.0);
1014    assert!(a.length().approx_eq(&1.0));
1015    a.set_length(1.5);
1016    assert!(a.length().approx_eq(&1.5));
1017    a.set_length(100.0);
1018    assert!(a.length().approx_eq(&100.0));
1019    a.set_length(-1.0);
1020    assert!(a.length().approx_eq(&1.0));
1021}
1022
1023#[test]
1024fn overlap() {
1025    assert!(LineSegment {
1026        from: point(0.0, 0.0),
1027        to: point(-1.0, 0.0),
1028    }
1029    .overlaps_line(&Line {
1030        point: point(100.0, 0.0),
1031        vector: vector(10.0, 0.0),
1032    }));
1033
1034    assert!(LineSegment {
1035        from: point(0.0, 0.0),
1036        to: point(1.0, 0.0),
1037    }
1038    .overlaps_line(&Line {
1039        point: point(0.0, 0.0),
1040        vector: vector(1.0, 0.0),
1041    }));
1042
1043    assert!(LineSegment {
1044        from: point(0.0, 0.0),
1045        to: point(1.0, 0.0),
1046    }
1047    .overlaps_segment(&LineSegment {
1048        from: point(0.0, 0.0),
1049        to: point(1.0, 0.0),
1050    }));
1051
1052    assert!(!LineSegment {
1053        from: point(0.0, 0.0),
1054        to: point(1.0, 0.0),
1055    }
1056    .overlaps_line(&Line {
1057        point: point(0.0, 1.0),
1058        vector: vector(1.0, 1.0),
1059    }));
1060}
1061
1062#[test]
1063fn contains_segment() {
1064    assert!(LineSegment {
1065        from: point(-1.0, 1.0),
1066        to: point(4.0, 1.0),
1067    }
1068    .contains_segment(&LineSegment {
1069        from: point(2.0, 1.0),
1070        to: point(1.0, 1.0),
1071    }));
1072}
1073
1074#[test]
1075fn horizontal_line_intersection() {
1076    let segment = LineSegment {
1077        from: point(1.0, 2.0),
1078        to: point(2.0, 3.0),
1079    };
1080
1081    assert_eq!(segment.horizontal_line_intersection_t(2.0), Some(0.0));
1082    assert_eq!(segment.horizontal_line_intersection_t(2.25), Some(0.25));
1083    assert_eq!(segment.horizontal_line_intersection_t(2.5), Some(0.5));
1084    assert_eq!(segment.horizontal_line_intersection_t(2.75), Some(0.75));
1085    assert_eq!(segment.horizontal_line_intersection_t(3.0), Some(1.0));
1086
1087    assert_eq!(segment.horizontal_line_intersection_t(1.5), None);
1088    assert_eq!(segment.horizontal_line_intersection_t(3.5), None);
1089
1090    let segment = LineSegment {
1091        from: point(2.0, 3.0),
1092        to: point(1.0, 2.0),
1093    };
1094
1095    assert_eq!(segment.horizontal_line_intersection_t(2.0), Some(1.0));
1096    assert_eq!(segment.horizontal_line_intersection_t(2.25), Some(0.75));
1097    assert_eq!(segment.horizontal_line_intersection_t(2.5), Some(0.5));
1098    assert_eq!(segment.horizontal_line_intersection_t(2.75), Some(0.25));
1099    assert_eq!(segment.horizontal_line_intersection_t(3.0), Some(0.0));
1100
1101    assert_eq!(segment.horizontal_line_intersection_t(1.5), None);
1102    assert_eq!(segment.horizontal_line_intersection_t(3.5), None);
1103}
1104
1105#[test]
1106fn intersection_on_endpoint() {
1107    let l1 = LineSegment {
1108        from: point(0.0, 0.0),
1109        to: point(0.0, 10.0),
1110    };
1111
1112    let l2 = LineSegment {
1113        from: point(0.0, 5.0),
1114        to: point(10.0, 5.0),
1115    };
1116
1117    assert_eq!(l1.intersection_t(&l2), Some((0.5, 0.0)));
1118    assert_eq!(l2.intersection_t(&l1), Some((0.0, 0.5)));
1119
1120    let l3 = LineSegment {
1121        from: point(10.0, 5.0),
1122        to: point(0.0, 5.0),
1123    };
1124
1125    assert_eq!(l1.intersection_t(&l3), Some((0.5, 1.0)));
1126    assert_eq!(l3.intersection_t(&l1), Some((1.0, 0.5)));
1127}
1128
1129#[test]
1130fn intersects_box() {
1131    let b = Box2D {
1132        min: point(1.0, 2.0),
1133        max: point(4.0, 4.0),
1134    };
1135
1136    assert!(!Line {
1137        point: point(0.0, 0.0),
1138        vector: vector(1.0, 0.0)
1139    }
1140    .intersects_box(&b));
1141    assert!(!Line {
1142        point: point(0.0, 0.0),
1143        vector: vector(0.0, 1.0)
1144    }
1145    .intersects_box(&b));
1146    assert!(!Line {
1147        point: point(10.0, 0.0),
1148        vector: vector(10.0, 10.0)
1149    }
1150    .intersects_box(&b));
1151    assert!(!Line {
1152        point: point(0.0, 10.0),
1153        vector: vector(10.0, 10.0)
1154    }
1155    .intersects_box(&b));
1156
1157    assert!(Line {
1158        point: point(1.5, 0.0),
1159        vector: vector(1.0, 6.0)
1160    }
1161    .intersects_box(&b));
1162    assert!(Line {
1163        point: point(1.5, 0.0),
1164        vector: vector(-1.0, 6.0)
1165    }
1166    .intersects_box(&b));
1167    assert!(Line {
1168        point: point(1.5, 2.5),
1169        vector: vector(1.0, 0.5)
1170    }
1171    .intersects_box(&b));
1172    assert!(Line {
1173        point: point(1.5, 2.5),
1174        vector: vector(-1.0, -2.0)
1175    }
1176    .intersects_box(&b));
1177}
1178
1179#[test]
1180fn clipped() {
1181    let b = Box2D {
1182        min: point(1.0, 2.0),
1183        max: point(3.0, 4.0),
1184    };
1185
1186    fn approx_eq(a: LineSegment<f32>, b: LineSegment<f32>) -> bool {
1187        let ok = a.from.approx_eq(&b.from) && a.to.approx_eq(&b.to);
1188        if !ok {
1189            std::println!("{a:?} != {b:?}");
1190        }
1191
1192        ok
1193    }
1194
1195    assert_eq!(
1196        LineSegment {
1197            from: point(0.0, 1.0),
1198            to: point(4.0, 1.0)
1199        }
1200        .clipped(&b),
1201        None
1202    );
1203    assert_eq!(
1204        LineSegment {
1205            from: point(0.0, 2.0),
1206            to: point(4.0, 2.0)
1207        }
1208        .clipped(&b),
1209        Some(LineSegment {
1210            from: point(1.0, 2.0),
1211            to: point(3.0, 2.0)
1212        })
1213    );
1214    assert_eq!(
1215        LineSegment {
1216            from: point(0.0, 3.0),
1217            to: point(4.0, 3.0)
1218        }
1219        .clipped(&b),
1220        Some(LineSegment {
1221            from: point(1.0, 3.0),
1222            to: point(3.0, 3.0)
1223        })
1224    );
1225    assert_eq!(
1226        LineSegment {
1227            from: point(0.0, 4.0),
1228            to: point(4.0, 4.0)
1229        }
1230        .clipped(&b),
1231        Some(LineSegment {
1232            from: point(1.0, 4.0),
1233            to: point(3.0, 4.0)
1234        })
1235    );
1236    assert_eq!(
1237        LineSegment {
1238            from: point(0.0, 5.0),
1239            to: point(4.0, 5.0)
1240        }
1241        .clipped(&b),
1242        None
1243    );
1244
1245    assert_eq!(
1246        LineSegment {
1247            from: point(4.0, 1.0),
1248            to: point(0.0, 1.0)
1249        }
1250        .clipped(&b),
1251        None
1252    );
1253    assert_eq!(
1254        LineSegment {
1255            from: point(4.0, 2.0),
1256            to: point(0.0, 2.0)
1257        }
1258        .clipped(&b),
1259        Some(LineSegment {
1260            from: point(3.0, 2.0),
1261            to: point(1.0, 2.0)
1262        })
1263    );
1264    assert_eq!(
1265        LineSegment {
1266            from: point(4.0, 3.0),
1267            to: point(0.0, 3.0)
1268        }
1269        .clipped(&b),
1270        Some(LineSegment {
1271            from: point(3.0, 3.0),
1272            to: point(1.0, 3.0)
1273        })
1274    );
1275    assert_eq!(
1276        LineSegment {
1277            from: point(4.0, 4.0),
1278            to: point(0.0, 4.0)
1279        }
1280        .clipped(&b),
1281        Some(LineSegment {
1282            from: point(3.0, 4.0),
1283            to: point(1.0, 4.0)
1284        })
1285    );
1286    assert_eq!(
1287        LineSegment {
1288            from: point(4.0, 5.0),
1289            to: point(0.0, 5.0)
1290        }
1291        .clipped(&b),
1292        None
1293    );
1294
1295    assert_eq!(
1296        LineSegment {
1297            from: point(0.0, 0.0),
1298            to: point(0.0, 5.0)
1299        }
1300        .clipped(&b),
1301        None
1302    );
1303    assert_eq!(
1304        LineSegment {
1305            from: point(1.0, 0.0),
1306            to: point(1.0, 5.0)
1307        }
1308        .clipped(&b),
1309        Some(LineSegment {
1310            from: point(1.0, 2.0),
1311            to: point(1.0, 4.0)
1312        })
1313    );
1314    assert_eq!(
1315        LineSegment {
1316            from: point(2.0, 0.0),
1317            to: point(2.0, 5.0)
1318        }
1319        .clipped(&b),
1320        Some(LineSegment {
1321            from: point(2.0, 2.0),
1322            to: point(2.0, 4.0)
1323        })
1324    );
1325    assert_eq!(
1326        LineSegment {
1327            from: point(3.0, 0.0),
1328            to: point(3.0, 5.0)
1329        }
1330        .clipped(&b),
1331        Some(LineSegment {
1332            from: point(3.0, 2.0),
1333            to: point(3.0, 4.0)
1334        })
1335    );
1336    assert_eq!(
1337        LineSegment {
1338            from: point(4.0, 0.0),
1339            to: point(4.0, 5.0)
1340        }
1341        .clipped(&b),
1342        None
1343    );
1344
1345    assert_eq!(
1346        LineSegment {
1347            from: point(0.0, 5.0),
1348            to: point(0.0, 0.0)
1349        }
1350        .clipped(&b),
1351        None
1352    );
1353    assert_eq!(
1354        LineSegment {
1355            from: point(1.0, 5.0),
1356            to: point(1.0, 0.0)
1357        }
1358        .clipped(&b),
1359        Some(LineSegment {
1360            from: point(1.0, 4.0),
1361            to: point(1.0, 2.0)
1362        })
1363    );
1364    assert_eq!(
1365        LineSegment {
1366            from: point(2.0, 5.0),
1367            to: point(2.0, 0.0)
1368        }
1369        .clipped(&b),
1370        Some(LineSegment {
1371            from: point(2.0, 4.0),
1372            to: point(2.0, 2.0)
1373        })
1374    );
1375    assert_eq!(
1376        LineSegment {
1377            from: point(3.0, 5.0),
1378            to: point(3.0, 0.0)
1379        }
1380        .clipped(&b),
1381        Some(LineSegment {
1382            from: point(3.0, 4.0),
1383            to: point(3.0, 2.0)
1384        })
1385    );
1386    assert_eq!(
1387        LineSegment {
1388            from: point(4.0, 5.0),
1389            to: point(4.0, 0.0)
1390        }
1391        .clipped(&b),
1392        None
1393    );
1394
1395    assert!(approx_eq(
1396        LineSegment {
1397            from: point(0.0, 2.0),
1398            to: point(4.0, 4.0)
1399        }
1400        .clipped(&b)
1401        .unwrap(),
1402        LineSegment {
1403            from: point(1.0, 2.5),
1404            to: point(3.0, 3.5)
1405        }
1406    ));
1407    assert!(approx_eq(
1408        LineSegment {
1409            from: point(4.0, 4.0),
1410            to: point(0.0, 2.0)
1411        }
1412        .clipped(&b)
1413        .unwrap(),
1414        LineSegment {
1415            from: point(3.0, 3.5),
1416            to: point(1.0, 2.5)
1417        }
1418    ));
1419
1420    let inside = [
1421        LineSegment {
1422            from: point(1.0, 2.0),
1423            to: point(3.0, 4.0),
1424        },
1425        LineSegment {
1426            from: point(1.5, 2.0),
1427            to: point(1.0, 4.0),
1428        },
1429        LineSegment {
1430            from: point(1.0, 3.0),
1431            to: point(2.0, 3.0),
1432        },
1433    ];
1434
1435    for segment in &inside {
1436        assert_eq!(segment.clipped(&b), Some(*segment));
1437        assert_eq!(segment.flip().clipped(&b), Some(segment.flip()));
1438    }
1439
1440    let outside = [
1441        LineSegment {
1442            from: point(2.0, 0.0),
1443            to: point(5.0, 3.0),
1444        },
1445        LineSegment {
1446            from: point(-20.0, 0.0),
1447            to: point(4.0, 8.0),
1448        },
1449    ];
1450
1451    for segment in &outside {
1452        assert_eq!(segment.clipped(&b), None);
1453        assert_eq!(segment.flip().clipped(&b), None);
1454    }
1455}
1456
1457#[test]
1458fn equation() {
1459    let lines = [
1460        Line {
1461            point: point(100.0f64, 20.0),
1462            vector: vector(-1.0, 3.0),
1463        },
1464        Line {
1465            point: point(-30.0, 150.0),
1466            vector: vector(10.0, 2.0),
1467        },
1468        Line {
1469            point: point(50.0, -10.0),
1470            vector: vector(5.0, -1.0),
1471        },
1472    ];
1473
1474    for line in &lines {
1475        let eqn = line.equation();
1476        use euclid::approxeq::ApproxEq;
1477        for t in [-100.0, -50.0, 0.0, 25.0, 325.0] {
1478            let p = line.point + line.vector * t;
1479            assert!(eqn.solve_y_for_x(p.x).unwrap().approx_eq(&p.y));
1480            assert!(eqn.solve_x_for_y(p.y).unwrap().approx_eq(&p.x));
1481        }
1482    }
1483}
lyon_geom/line.rs

lyon_geom/
line.rs
