parry2d/utils/
point_in_triangle.rs

1//! Function to check if a point is inside a triangle and related functions.
2
3use crate::math::{Point, Real};
4
5#[derive(Eq, PartialEq, Debug, Copy, Clone)]
6/// The orientation or winding direction of a corner or polygon.
7pub enum Orientation {
8    /// Counter-clockwise
9    Ccw,
10    /// Clockwise
11    Cw,
12    /// Neither (a straight line)
13    None,
14}
15
16/// Returns the direction of a line through `p1`, `p2` and `p3`.
17///
18/// Counter-clockwise example:
19/// o p1
20///  .        o p3
21///   .     .
22///    .  .
23///     o p2
24///
25/// Clockwise example:
26///     o p2
27///    .  .
28///   .     .
29///  .        o p3
30/// o p1
31pub fn corner_direction(p1: &Point<Real>, p2: &Point<Real>, p3: &Point<Real>) -> Orientation {
32    let v1 = p1 - p2;
33    let v2 = p3 - p2;
34    let cross: Real = v1.perp(&v2);
35
36    match cross
37        .partial_cmp(&0.0)
38        .expect("Found NaN while computing corner direction.")
39    {
40        core::cmp::Ordering::Less => Orientation::Ccw,
41        core::cmp::Ordering::Equal => Orientation::None,
42        core::cmp::Ordering::Greater => Orientation::Cw,
43    }
44}
45
46/// Returns `true` if point `p` is in triangle with corners `v1`, `v2` and `v3`.
47/// Returns `None` if the triangle is invalid i.e. all points are the same or on a straight line.
48pub fn is_point_in_triangle(
49    p: &Point<Real>,
50    v1: &Point<Real>,
51    v2: &Point<Real>,
52    v3: &Point<Real>,
53) -> Option<bool> {
54    let d1 = corner_direction(p, v1, v2);
55    let d2 = corner_direction(p, v2, v3);
56    let d3 = corner_direction(p, v3, v1);
57
58    let has_cw = d1 == Orientation::Cw || d2 == Orientation::Cw || d3 == Orientation::Cw;
59    let has_ccw = d1 == Orientation::Ccw || d2 == Orientation::Ccw || d3 == Orientation::Ccw;
60
61    if d1 == Orientation::None && d2 == Orientation::None && d3 == Orientation::None {
62        None
63    } else {
64        Some(!(has_cw && has_ccw))
65    }
66}
parry2d/utils/point_in_triangle.rs

parry2d/utils/
point_in_triangle.rs
