implicit_predicates/
lib.rs

1//! Exact geometric predicates over explicit and implicit points.
2//!
3//! An implicit point is defined by an unevaluated construction, such as a
4//! point on an edge or inside a triangle. Predicates receive the construction
5//! itself and return the exact sign, without rounding the point's
6//! coordinates.
7//!
8//! **Status: early development.** Today the crate provides [`orient3d`] for
9//! explicit points, given as `[f64; 3]`; implicit points do not exist yet.
10//! Like every predicate of the crate, it is generated by
11//! `implicit-predicates-gen` from a short definition: a floating-point filter
12//! decides the common cases, and exact stages built on the expansions of
13//! `implicit-predicates-core` decide the rest.
14//!
15//! ```
16//! use implicit_predicates::{Sign, orient3d};
17//!
18//! let (a, b, c) = ([1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]);
19//! // a, b and c appear counter-clockwise from (1, 1, 1), above the plane.
20//! assert_eq!(orient3d(&a, &b, &c, &[1.0, 1.0, 1.0]), Some(Sign::Negative));
21//! assert_eq!(orient3d(&a, &b, &c, &[0.0, 0.0, 0.0]), Some(Sign::Positive));
22//! // A point on the plane.
23//! assert_eq!(orient3d(&a, &b, &c, &[0.5, 0.25, 0.25]), Some(Sign::Zero));
24//! ```
25
26#![cfg_attr(not(feature = "std"), no_std)]
27#![forbid(unsafe_code)]
28
29mod generated;
30
31pub use implicit_predicates_core::Sign;
32
33/// The orientation of `d` with respect to the plane through `a`, `b` and
34/// `c`: the exact sign of the determinant
35///
36/// ```text
37/// | a.x - d.x   a.y - d.y   a.z - d.z |
38/// | b.x - d.x   b.y - d.y   b.z - d.z |
39/// | c.x - d.x   c.y - d.y   c.z - d.z |
40/// ```
41///
42/// The sign is [`Sign::Positive`] when `d` lies below the plane, taking
43/// "above" to be the side from which `a`, `b` and `c` appear in
44/// counter-clockwise order; [`Sign::Negative`] when `d` lies above it; and
45/// [`Sign::Zero`] when the four points are coplanar. This is the convention
46/// of Shewchuk's `orient3d`. Swapping any two points flips the sign.
47///
48/// # When the result is `None`
49///
50/// The result is `Some` whenever every nonzero coordinate has a magnitude
51/// between `2^-188` and `2^239` (about `2.5e-57` and `8.8e71`): the last
52/// two stages evaluate with expansions, one on coordinates up to `2^238` and
53/// the other on coordinates up to `2^239`, and together they decide every
54/// such input. Outside that range the sign is still exact when it is
55/// returned, but `None` is returned when no stage can decide: always when
56/// some coordinate is not finite, and otherwise only when the
57/// floating-point filter and the stage on exact differences of coordinates
58/// cannot decide either. This is provisional: a later version will decide
59/// every finite input.
60///
61/// # Examples
62///
63/// ```
64/// use implicit_predicates::{Sign, orient3d};
65///
66/// let (a, b, c) = ([1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]);
67/// // a, b and c appear counter-clockwise from (1, 1, 1), above the plane.
68/// assert_eq!(orient3d(&a, &b, &c, &[1.0, 1.0, 1.0]), Some(Sign::Negative));
69/// assert_eq!(orient3d(&a, &b, &c, &[0.0, 0.0, 0.0]), Some(Sign::Positive));
70/// // A point on the plane, and one that is not a point.
71/// assert_eq!(orient3d(&a, &b, &c, &[0.5, 0.25, 0.25]), Some(Sign::Zero));
72/// assert_eq!(orient3d(&a, &b, &c, &[f64::NAN, 0.0, 0.0]), None);
73/// ```
74#[inline]
75pub fn orient3d(a: &[f64; 3], b: &[f64; 3], c: &[f64; 3], d: &[f64; 3]) -> Option<Sign> {
76    generated::orient3d::staged([a, b, c, d])
77}
78
79/// The individual stages of each predicate, for tests and benchmarks.
80#[doc(hidden)]
81pub mod stages {
82    pub use crate::generated::orient3d;
83}
implicit_predicates/lib.rs

implicit_predicates/
lib.rs
