arris_math/
predicates.rs

1//! Exact 2D orientation and in-circle predicates over `robust`.
2//!
3//! These decide combinatorial questions — which side of a segment a point
4//! lies on, whether four points are cocircular — *exactly* on the stored
5//! coordinates, with no tolerance: a predicate is never softened by a
6//! tolerance and a tolerance comparison never pretends to be exact
7//! (`docs/DATA-MODEL.md` §Tolerances). The arithmetic is Shewchuk's
8//! adaptive-precision scheme as implemented by the `robust` crate.
9//!
10//! ```
11//! use arris_math::Point2;
12//! use arris_math::predicates::{Sign, incircle, orient2d};
13//!
14//! let a = Point2::new(0.0, 0.0);
15//! let b = Point2::new(1.0, 0.0);
16//! let c = Point2::new(0.0, 1.0);
17//! assert_eq!(orient2d(a, b, c), Sign::Positive); // counter-clockwise
18//! assert_eq!(orient2d(a, b, Point2::new(2.0, 0.0)), Sign::Zero); // collinear
19//! assert_eq!(incircle(a, b, c, Point2::new(0.25, 0.25)), Sign::Positive); // inside
20//! assert_eq!(incircle(a, b, c, Point2::new(1.0, 1.0)), Sign::Zero); // on the circle
21//! ```
22
23use core::cmp::Ordering;
24
25use robust::Coord;
26
27use crate::Point2;
28
29/// The exact sign of a predicate's determinant.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
31pub enum Sign {
32    /// Below zero.
33    Negative,
34    /// Exactly zero: the degenerate configuration.
35    Zero,
36    /// Above zero.
37    Positive,
38}
39
40impl Sign {
41    /// The sign of `x`; NaN counts as zero, since it has no sign.
42    pub fn of(x: f64) -> Sign {
43        match x.partial_cmp(&0.0) {
44            Some(Ordering::Less) => Sign::Negative,
45            Some(Ordering::Greater) => Sign::Positive,
46            Some(Ordering::Equal) | None => Sign::Zero,
47        }
48    }
49
50    /// The opposite sign; zero stays zero.
51    pub fn flipped(self) -> Sign {
52        match self {
53            Sign::Negative => Sign::Positive,
54            Sign::Zero => Sign::Zero,
55            Sign::Positive => Sign::Negative,
56        }
57    }
58}
59
60/// The exact sign of twice the signed area of the triangle `a b c`:
61/// `Positive` when the points turn counter-clockwise (`c` is left of the
62/// directed line `a → b`), `Negative` when clockwise, `Zero` when
63/// collinear.
64pub fn orient2d(a: Point2, b: Point2, c: Point2) -> Sign {
65    Sign::of(robust::orient2d(coord(a), coord(b), coord(c)))
66}
67
68/// The exact position of `d` against the circle through `a`, `b`, `c`,
69/// which must be counter-clockwise: `Positive` inside, `Negative` outside,
70/// `Zero` on the circle. For a clockwise `a b c` the signs swap; for a
71/// collinear one the "circle" is the line and the result is `Zero` for
72/// every `d` on it.
73pub fn incircle(a: Point2, b: Point2, c: Point2, d: Point2) -> Sign {
74    Sign::of(robust::incircle(coord(a), coord(b), coord(c), coord(d)))
75}
76
77fn coord(p: Point2) -> Coord<f64> {
78    Coord { x: p.x, y: p.y }
79}
arris_math/predicates.rs

arris_math/
predicates.rs
