parry2d/utils/
point_in_triangle.rs

1//! Function to check if a point is inside a triangle and related functions.
2
3use crate::math::{Real, Vector};
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: Vector, p2: Vector, p3: Vector) -> Orientation {
32    let v1 = p1 - p2;
33    let v2 = p3 - p2;
34    let cross: Real = v1.perp_dot(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(p: Vector, v1: Vector, v2: Vector, v3: Vector) -> Option<bool> {
49    let d1 = corner_direction(p, v1, v2);
50    let d2 = corner_direction(p, v2, v3);
51    let d3 = corner_direction(p, v3, v1);
52
53    let has_cw = d1 == Orientation::Cw || d2 == Orientation::Cw || d3 == Orientation::Cw;
54    let has_ccw = d1 == Orientation::Ccw || d2 == Orientation::Ccw || d3 == Orientation::Ccw;
55
56    if d1 == Orientation::None && d2 == Orientation::None && d3 == Orientation::None {
57        None
58    } else {
59        Some(!(has_cw && has_ccw))
60    }
61}
parry2d/utils/point_in_triangle.rs

parry2d/utils/
point_in_triangle.rs
