flo_curves 0.8.0

Library for manipulating Bezier curves
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

use super::curve::*;
use super::super::geo::*;
use super::super::line::*;
use super::super::consts::*;

///
/// If `curve2` overlaps `curve1`, returns two sets of `t` values (those for `curve1` and those for `curve2`)
///
pub fn overlapping_region<C1: BezierCurve, C2: BezierCurve>(curve1: &C1, curve2: &C2) -> Option<((f64, f64), (f64, f64))>
where   C1::Point:  Coordinate+Coordinate2D,
        C2:         BezierCurve<Point=C1::Point>,
{
    // 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
    // An exception for this is if the two curves are collinear lines, in which case the control points don't matter

    // Start by assuming that curve 2 overlaps curve 1 completely
    let mut c2_t1 = 0.0;
    let mut c2_t2 = 1.0;
    let mut overlapping_endpoints = false;

    // The start and end points of curve1 should be on curve2
    let c2_start    = curve2.start_point();
    let c2_end      = curve2.end_point();

    let c1_t1 = if let Some(t) = curve1.t_for_point(&c2_start) {
        // Start point is on the curve
        t
    } else if let Some(t) = curve2.t_for_point(&curve1.start_point()) {
        // curve1 starts on a point of curve2
        c2_t1 = t;
        0.0
    } else if let (Some(t1), Some(t2)) = (curve1.t_for_point(&curve2.end_point()), curve2.t_for_point(&curve1.end_point())) {
        // End points are part of both curves, but start points are not
        c2_t1 = 1.0;
        c2_t2 = t2;

        overlapping_endpoints = true;
        t1
    } else {
        // Neither point is on the curve
        return None;
    };

    let c1_t2 = if overlapping_endpoints {
        // Rare case: the curves overlap at the end points only
        1.0
    } else if let Some(t) = curve1.t_for_point(&c2_end) {
        // End point is on the curve
        t
    } else if let Some(t) = curve2.t_for_point(&curve1.end_point()) {
        // curve1 ends on a point of curve2
        if c1_t1 > 0.9 && c2_start.is_near_to(&curve1.end_point(), SMALL_DISTANCE) {
            // Curve1 ends on the start point of c2 (ie, we've found c1_t1 again)
            // Curve1 does not match c2_end
            if let Some(t) = curve2.t_for_point(&curve1.start_point()) {
                // Curve1's start point is on curve2
                c2_t2 = t;
                0.0
            } else {
                return None;
            }
        } else {
            // No overlap
            c2_t2 = t;
            1.0
        }
    } else if let Some(t) = curve2.t_for_point(&curve1.start_point()) {
        // 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)
        c2_t2 = t;
        0.0
    } else {
        // End point is not on the curve
        return None;
    };

    // If we just found one point where the curve overlaps, then say that they didn't
    if (c1_t1-c1_t2).abs() < SMALL_T_DISTANCE || (c2_t1-c2_t2).abs() < SMALL_T_DISTANCE {
        return None;
    }

    if (c1_t1-c1_t2).abs() < 0.01 && (c1_t1 <= 0.0 || c1_t1 >= 1.0 || c1_t2 <= 0.0 || c1_t2 >= 1.0) {
        // Might be a very tiny overlap at the end or the beginning
        let c1_start    = curve1.point_at_pos(c1_t1);
        let c1_end      = curve1.point_at_pos(c1_t2);

        if c1_start.is_near_to(&c1_end, SMALL_DISTANCE) {
            return None;
        }
    }

    // If curve1 and curve2 are collinear - two overlapping lines - we've already got the results (and the control points will differ anyway)
    #[inline]
    fn is_collinear<P: Coordinate2D>(p: &P, LineCoefficients(a, b, c): &LineCoefficients) -> bool {
        (a*p.x() + b*p.y() + c).abs() < SMALL_DISTANCE
    }

    let coeff               = (curve1.start_point(), curve1.end_point()).coefficients();
    let (c1_cp1, c1_cp2)    = curve1.control_points();

    if is_collinear(&c1_cp1, &coeff) && is_collinear(&c1_cp2, &coeff)
        && is_collinear(&curve2.start_point(), &coeff) && is_collinear(&curve2.end_point(), &coeff) {
        let (c2_cp1, c2_cp2) = curve2.control_points();

        if is_collinear(&c2_cp1, &coeff) && is_collinear(&c2_cp2, &coeff) {
            return Some(((c1_t1, c1_t2), (c2_t1, c2_t2)));
        }
    }

    // Start and end points match at t1, t2
    #[inline]
    fn close_enough<P: Coordinate>(p1: &P, p2: &P) -> bool {
        p1.is_near_to(p2, SMALL_DISTANCE)
    }

    // Get the control points for the two curves
    #[inline]
    fn control_points<C: BezierCurve>(curve: &C, t1: f64, t2: f64) -> (C::Point, C::Point)
    where 
        C::Point: Coordinate+Coordinate2D,  
    {
        if t2 < t1 {
            let (cp2, cp1) = curve.section(t2, t1).control_points();
            (cp1, cp2)
        } else {
            curve.section(t1, t2).control_points()
        }
    }

    let (c2_cp1, c2_cp2) = if c2_t1 != 0.0 || c2_t2 != 1.0 {
        control_points(curve2, c2_t1, c2_t2)
    } else {
        curve2.control_points()
    };

    let (c1_cp1, c1_cp2) = control_points(curve1, c1_t1, c1_t2);

    // If they're about the same, we've found an overlapping region
    if close_enough(&c1_cp1, &c2_cp1) && close_enough(&c1_cp2, &c2_cp2) {
        Some(((c1_t1, c1_t2), (c2_t1, c2_t2)))
    } else {
        None
    }
}