use_orientation/
lib.rs

1#![forbid(unsafe_code)]
2#![doc = include_str!("../README.md")]
3
4use use_coordinate::GeometryError;
5use use_point::Point2;
6
7/// The winding order of three 2D points.
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum Orientation2 {
10    /// Points wind in clockwise order.
11    Clockwise,
12    /// Points wind in counterclockwise order.
13    CounterClockwise,
14    /// Points are collinear.
15    Collinear,
16}
17
18/// Returns twice the signed area of the triangle formed by three 2D points.
19#[must_use]
20pub fn signed_twice_area_2d(a: Point2, b: Point2, c: Point2) -> f64 {
21    let ab_x = b.x() - a.x();
22    let ab_y = b.y() - a.y();
23    let ac_x = c.x() - a.x();
24    let ac_y = c.y() - a.y();
25
26    ab_x.mul_add(ac_y, -(ab_y * ac_x))
27}
28
29/// Returns the winding order of three 2D points.
30#[must_use]
31pub fn orientation_2d(a: Point2, b: Point2, c: Point2) -> Orientation2 {
32    let signed_area = signed_twice_area_2d(a, b, c);
33
34    if signed_area > 0.0 {
35        Orientation2::CounterClockwise
36    } else if signed_area < 0.0 {
37        Orientation2::Clockwise
38    } else {
39        Orientation2::Collinear
40    }
41}
42
43/// Returns the winding order of three 2D points using an explicit area tolerance.
44///
45/// # Errors
46///
47/// Returns [`GeometryError::NonFiniteTolerance`] when `tolerance` is `NaN` or
48/// infinite.
49///
50/// Returns [`GeometryError::NegativeTolerance`] when `tolerance` is negative.
51pub fn orientation_2d_with_tolerance(
52    a: Point2,
53    b: Point2,
54    c: Point2,
55    tolerance: f64,
56) -> Result<Orientation2, GeometryError> {
57    let tolerance = GeometryError::validate_tolerance(tolerance)?;
58    let signed_area = signed_twice_area_2d(a, b, c);
59
60    Ok(if signed_area > tolerance {
61        Orientation2::CounterClockwise
62    } else if signed_area < -tolerance {
63        Orientation2::Clockwise
64    } else {
65        Orientation2::Collinear
66    })
67}
68
69/// Returns the winding order of three 2D points with finite coordinates.
70///
71/// # Errors
72///
73/// Returns [`GeometryError::NonFiniteComponent`] when any input point contains
74/// a non-finite coordinate.
75pub fn try_orientation_2d(a: Point2, b: Point2, c: Point2) -> Result<Orientation2, GeometryError> {
76    let a = a.validate()?;
77    let b = b.validate()?;
78    let c = c.validate()?;
79
80    Ok(orientation_2d(a, b, c))
81}
82
83/// Returns the winding order of three finite 2D points using an explicit area tolerance.
84///
85/// # Errors
86///
87/// Returns [`GeometryError::NonFiniteComponent`] when any input point contains
88/// a non-finite coordinate.
89///
90/// Returns [`GeometryError::NonFiniteTolerance`] when `tolerance` is `NaN` or
91/// infinite.
92///
93/// Returns [`GeometryError::NegativeTolerance`] when `tolerance` is negative.
94pub fn try_orientation_2d_with_tolerance(
95    a: Point2,
96    b: Point2,
97    c: Point2,
98    tolerance: f64,
99) -> Result<Orientation2, GeometryError> {
100    let a = a.validate()?;
101    let b = b.validate()?;
102    let c = c.validate()?;
103
104    orientation_2d_with_tolerance(a, b, c, tolerance)
105}
106
107#[cfg(test)]
108mod tests {
109    use super::{
110        Orientation2, orientation_2d, orientation_2d_with_tolerance, signed_twice_area_2d,
111        try_orientation_2d, try_orientation_2d_with_tolerance,
112    };
113    use use_coordinate::GeometryError;
114    use use_point::Point2;
115
116    fn approx_eq(left: f64, right: f64) -> bool {
117        (left - right).abs() < 1.0e-10
118    }
119
120    #[test]
121    fn computes_counterclockwise_orientation() {
122        assert_eq!(
123            orientation_2d(
124                Point2::new(0.0, 0.0),
125                Point2::new(4.0, 0.0),
126                Point2::new(0.0, 3.0)
127            ),
128            Orientation2::CounterClockwise
129        );
130    }
131
132    #[test]
133    fn computes_clockwise_orientation() {
134        assert_eq!(
135            orientation_2d(
136                Point2::new(0.0, 0.0),
137                Point2::new(0.0, 3.0),
138                Point2::new(4.0, 0.0)
139            ),
140            Orientation2::Clockwise
141        );
142    }
143
144    #[test]
145    fn computes_collinear_orientation() {
146        assert_eq!(
147            orientation_2d(
148                Point2::new(0.0, 0.0),
149                Point2::new(1.0, 1.0),
150                Point2::new(2.0, 2.0)
151            ),
152            Orientation2::Collinear
153        );
154    }
155
156    #[test]
157    fn computes_signed_twice_area() {
158        assert!(approx_eq(
159            signed_twice_area_2d(
160                Point2::new(0.0, 0.0),
161                Point2::new(4.0, 0.0),
162                Point2::new(0.0, 3.0)
163            ),
164            12.0
165        ));
166    }
167
168    #[test]
169    fn computes_try_orientation_for_finite_points() {
170        assert_eq!(
171            try_orientation_2d(
172                Point2::new(0.0, 0.0),
173                Point2::new(4.0, 0.0),
174                Point2::new(0.0, 3.0)
175            ),
176            Ok(Orientation2::CounterClockwise)
177        );
178    }
179
180    #[test]
181    fn rejects_try_orientation_for_non_finite_points() {
182        assert_eq!(
183            try_orientation_2d(
184                Point2::new(0.0, 0.0),
185                Point2::new(4.0, 0.0),
186                Point2::new(0.0, f64::INFINITY)
187            ),
188            Err(GeometryError::NonFiniteComponent {
189                type_name: "Point2",
190                component: "y",
191                value: f64::INFINITY,
192            })
193        );
194    }
195
196    #[test]
197    fn computes_tolerance_based_orientation() {
198        assert_eq!(
199            orientation_2d_with_tolerance(
200                Point2::new(0.0, 0.0),
201                Point2::new(1.0, 1.0),
202                Point2::new(2.0, 2.0 + 1.0e-12),
203                1.0e-11
204            ),
205            Ok(Orientation2::Collinear)
206        );
207        assert_eq!(
208            try_orientation_2d_with_tolerance(
209                Point2::new(0.0, 0.0),
210                Point2::new(4.0, 0.0),
211                Point2::new(0.0, 3.0),
212                0.0
213            ),
214            Ok(Orientation2::CounterClockwise)
215        );
216    }
217
218    #[test]
219    fn rejects_invalid_orientation_tolerance() {
220        assert_eq!(
221            orientation_2d_with_tolerance(
222                Point2::new(0.0, 0.0),
223                Point2::new(1.0, 0.0),
224                Point2::new(0.0, 1.0),
225                -1.0
226            ),
227            Err(GeometryError::NegativeTolerance(-1.0))
228        );
229    }
230}
use_orientation/lib.rs

use_orientation/
lib.rs
