use_geometry/
orientation.rs

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

use_geometry/
orientation.rs
