flo_curves/bezier/
overlaps.rs

1use super::curve::*;
2use super::super::geo::*;
3use super::super::line::*;
4use super::super::consts::*;
5
6///
7/// If `curve2` overlaps `curve1`, returns two sets of `t` values (those for `curve1` and those for `curve2`)
8///
9pub fn overlapping_region<C1: BezierCurve, C2: BezierCurve>(curve1: &C1, curve2: &C2) -> Option<((f64, f64), (f64, f64))>
10where   C1::Point:  Coordinate+Coordinate2D,
11        C2:         BezierCurve<Point=C1::Point>,
12{
13    // Two curves are overlapping if two of the four start/end points lies on the other curve and the control points are the same for those points
14    // An exception for this is if the two curves are collinear lines, in which case the control points don't matter
15
16    // Start by assuming that curve 2 overlaps curve 1 completely
17    let mut c2_t1 = 0.0;
18    let mut c2_t2 = 1.0;
19    let mut overlapping_endpoints = false;
20
21    // The start and end points of curve1 should be on curve2
22    let c2_start    = curve2.start_point();
23    let c2_end      = curve2.end_point();
24
25    let c1_t1 = if let Some(t) = curve1.t_for_point(&c2_start) {
26        // Start point is on the curve
27        t
28    } else if let Some(t) = curve2.t_for_point(&curve1.start_point()) {
29        // curve1 starts on a point of curve2
30        c2_t1 = t;
31        0.0
32    } else if let (Some(t1), Some(t2)) = (curve1.t_for_point(&curve2.end_point()), curve2.t_for_point(&curve1.end_point())) {
33        // End points are part of both curves, but start points are not
34        c2_t1 = 1.0;
35        c2_t2 = t2;
36
37        overlapping_endpoints = true;
38        t1
39    } else {
40        // Neither point is on the curve
41        return None;
42    };
43
44    let c1_t2 = if overlapping_endpoints {
45        // Rare case: the curves overlap at the end points only
46        1.0
47    } else if let Some(t) = curve1.t_for_point(&c2_end) {
48        // End point is on the curve
49        t
50    } else if let Some(t) = curve2.t_for_point(&curve1.end_point()) {
51        // curve1 ends on a point of curve2
52        if c1_t1 > 0.9 && c2_start.is_near_to(&curve1.end_point(), SMALL_DISTANCE) {
53            // Curve1 ends on the start point of c2 (ie, we've found c1_t1 again)
54            // Curve1 does not match c2_end
55            if let Some(t) = curve2.t_for_point(&curve1.start_point()) {
56                // Curve1's start point is on curve2
57                c2_t2 = t;
58                0.0
59            } else {
60                return None;
61            }
62        } else {
63            // No overlap
64            c2_t2 = t;
65            1.0
66        }
67    } else if let Some(t) = curve2.t_for_point(&curve1.start_point()) {
68        // curve1 starts on a point of curve2 (which will be an extra point if curve1 starts on a point of curve2, case where this is the only point is handled below)
69        c2_t2 = t;
70        0.0
71    } else {
72        // End point is not on the curve
73        return None;
74    };
75
76    // If we just found one point where the curve overlaps, then say that they didn't
77    if (c1_t1-c1_t2).abs() < SMALL_T_DISTANCE || (c2_t1-c2_t2).abs() < SMALL_T_DISTANCE {
78        return None;
79    }
80
81    if (c1_t1-c1_t2).abs() < 0.01 && (c1_t1 <= 0.0 || c1_t1 >= 1.0 || c1_t2 <= 0.0 || c1_t2 >= 1.0) {
82        // Might be a very tiny overlap at the end or the beginning
83        let c1_start    = curve1.point_at_pos(c1_t1);
84        let c1_end      = curve1.point_at_pos(c1_t2);
85
86        if c1_start.is_near_to(&c1_end, SMALL_DISTANCE) {
87            return None;
88        }
89    }
90
91    // If curve1 and curve2 are collinear - two overlapping lines - we've already got the results (and the control points will differ anyway)
92    #[inline]
93    fn is_collinear<P: Coordinate2D>(p: &P, LineCoefficients(a, b, c): &LineCoefficients) -> bool {
94        (a*p.x() + b*p.y() + c).abs() < SMALL_DISTANCE
95    }
96
97    let coeff               = (curve1.start_point(), curve1.end_point()).coefficients();
98    let (c1_cp1, c1_cp2)    = curve1.control_points();
99
100    if is_collinear(&c1_cp1, &coeff) && is_collinear(&c1_cp2, &coeff)
101        && is_collinear(&curve2.start_point(), &coeff) && is_collinear(&curve2.end_point(), &coeff) {
102        let (c2_cp1, c2_cp2) = curve2.control_points();
103
104        if is_collinear(&c2_cp1, &coeff) && is_collinear(&c2_cp2, &coeff) {
105            return Some(((c1_t1, c1_t2), (c2_t1, c2_t2)));
106        }
107    }
108
109    // Start and end points match at t1, t2
110    #[inline]
111    fn close_enough<P: Coordinate>(p1: &P, p2: &P) -> bool {
112        p1.is_near_to(p2, SMALL_DISTANCE)
113    }
114
115    // Get the control points for the two curves
116    #[inline]
117    fn control_points<C: BezierCurve>(curve: &C, t1: f64, t2: f64) -> (C::Point, C::Point)
118    where 
119        C::Point: Coordinate+Coordinate2D,  
120    {
121        if t2 < t1 {
122            let (cp2, cp1) = curve.section(t2, t1).control_points();
123            (cp1, cp2)
124        } else {
125            curve.section(t1, t2).control_points()
126        }
127    }
128
129    let (c2_cp1, c2_cp2) = if c2_t1 != 0.0 || c2_t2 != 1.0 {
130        control_points(curve2, c2_t1, c2_t2)
131    } else {
132        curve2.control_points()
133    };
134
135    let (c1_cp1, c1_cp2) = control_points(curve1, c1_t1, c1_t2);
136
137    // If they're about the same, we've found an overlapping region
138    if close_enough(&c1_cp1, &c2_cp1) && close_enough(&c1_cp2, &c2_cp2) {
139        Some(((c1_t1, c1_t2), (c2_t1, c2_t2)))
140    } else {
141        None
142    }
143}
flo_curves/bezier/overlaps.rs

flo_curves/bezier/
overlaps.rs
