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

use euclid::{Point2D, Vector2D};

/// How something may be oriented.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum Orientation {
    /// The points are arranged in a clockwise direction.
    Clockwise,
    /// The points are arranged in an anti-clockwise direction.
    Anticlockwise,
    /// The points are collinear.
    Collinear,
}

impl Orientation {
    /// Find the orientation of 3 [`Point2D`]s.
    pub fn of<S>(
        first: Point2D<f64, S>,
        second: Point2D<f64, S>,
        third: Point2D<f64, S>,
    ) -> Orientation {
        let value = (second.y - first.y) * (third.x - second.x)
            - (second.x - first.x) * (third.y - second.y);

        if value > 0.0 {
            Orientation::Clockwise
        } else if value < 0.0 {
            Orientation::Anticlockwise
        } else {
            Orientation::Collinear
        }
    }
}

/// Find the centre of an arc which passes through 3 [`Point2D`]s.
///
/// # Note
///
/// If the points are collinear then the problem is ambiguous, the radius
/// effectively becomes infinite and our centre could be literally anywhere.
///
/// ```rust
/// # type Point = euclid::default::Point2D<f64>;
/// let first = Point::new(0.0, 0.0);
/// let second = Point::new(1.0, 0.0);
/// let third = Point::new(25.0, 0.0);
///
/// let got = arcs_core::centre_of_three_points(first, second, third);
///
/// assert!(got.is_none());
/// ```
pub fn centre_of_three_points<S>(
    first: Point2D<f64, S>,
    second: Point2D<f64, S>,
    third: Point2D<f64, S>,
) -> Option<Point2D<f64, S>> {
    // it's easier to do the math using vectors, but for semantic correctness we
    // accept points
    let first = first.to_vector();
    let second = second.to_vector();
    let third = third.to_vector();

    let temp = Vector2D::dot(second, second);
    let bc = (Vector2D::dot(first, first) - temp) / 2.0;
    let cd = (temp - third.x * third.x - third.y * third.y) / 2.0;
    let determinant = (first.x - second.x) * (second.y - third.y)
        - (second.x - third.x) * (first.y - second.y);

    if determinant == 0.0 {
        // the points are collinear
        return None;
    }

    let x =
        (bc * (second.y - third.y) - cd * (first.y - second.y)) / determinant;
    let y =
        ((first.x - second.x) * cd - (second.x - third.x) * bc) / determinant;

    Some(Point2D::new(x, y))
}

#[cfg(test)]
mod tests {
    use super::*;
    use euclid::default::Point2D;

    #[test]
    fn find_centre_of_three_points() {
        let a = Point2D::new(1.0, 0.0);
        let b = Point2D::new(-1.0, 0.0);
        let c = Point2D::new(0.0, 1.0);

        let centre = centre_of_three_points(a, b, c).unwrap();

        assert_eq!(centre, Point2D::zero());
    }
}