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