implicit-predicates 0.0.1

Exact geometric predicates over explicit and implicit points
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

//! Exact geometric predicates over explicit and implicit points.
//!
//! An implicit point is defined by an unevaluated construction, such as a
//! point on an edge or inside a triangle. Predicates receive the construction
//! itself and return the exact sign, without rounding the point's
//! coordinates.
//!
//! **Status: early development.** Today the crate provides [`orient3d`] for
//! explicit points, given as `[f64; 3]`; implicit points do not exist yet.
//! Like every predicate of the crate, it is generated by
//! `implicit-predicates-gen` from a short definition: a floating-point filter
//! decides the common cases, and exact stages built on the expansions of
//! `implicit-predicates-core` decide the rest.
//!
//! ```
//! use implicit_predicates::{Sign, orient3d};
//!
//! let (a, b, c) = ([1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]);
//! // a, b and c appear counter-clockwise from (1, 1, 1), above the plane.
//! assert_eq!(orient3d(&a, &b, &c, &[1.0, 1.0, 1.0]), Some(Sign::Negative));
//! assert_eq!(orient3d(&a, &b, &c, &[0.0, 0.0, 0.0]), Some(Sign::Positive));
//! // A point on the plane.
//! assert_eq!(orient3d(&a, &b, &c, &[0.5, 0.25, 0.25]), Some(Sign::Zero));
//! ```

#![cfg_attr(not(feature = "std"), no_std)]
#![forbid(unsafe_code)]

mod generated;

pub use implicit_predicates_core::Sign;

/// The orientation of `d` with respect to the plane through `a`, `b` and
/// `c`: the exact sign of the determinant
///
/// ```text
/// | a.x - d.x   a.y - d.y   a.z - d.z |
/// | b.x - d.x   b.y - d.y   b.z - d.z |
/// | c.x - d.x   c.y - d.y   c.z - d.z |
/// ```
///
/// The sign is [`Sign::Positive`] when `d` lies below the plane, taking
/// "above" to be the side from which `a`, `b` and `c` appear in
/// counter-clockwise order; [`Sign::Negative`] when `d` lies above it; and
/// [`Sign::Zero`] when the four points are coplanar. This is the convention
/// of Shewchuk's `orient3d`. Swapping any two points flips the sign.
///
/// # When the result is `None`
///
/// The result is `Some` whenever every nonzero coordinate has a magnitude
/// between `2^-188` and `2^239` (about `2.5e-57` and `8.8e71`): the last
/// two stages evaluate with expansions, one on coordinates up to `2^238` and
/// the other on coordinates up to `2^239`, and together they decide every
/// such input. Outside that range the sign is still exact when it is
/// returned, but `None` is returned when no stage can decide: always when
/// some coordinate is not finite, and otherwise only when the
/// floating-point filter and the stage on exact differences of coordinates
/// cannot decide either. This is provisional: a later version will decide
/// every finite input.
///
/// # Examples
///
/// ```
/// use implicit_predicates::{Sign, orient3d};
///
/// let (a, b, c) = ([1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]);
/// // a, b and c appear counter-clockwise from (1, 1, 1), above the plane.
/// assert_eq!(orient3d(&a, &b, &c, &[1.0, 1.0, 1.0]), Some(Sign::Negative));
/// assert_eq!(orient3d(&a, &b, &c, &[0.0, 0.0, 0.0]), Some(Sign::Positive));
/// // A point on the plane, and one that is not a point.
/// assert_eq!(orient3d(&a, &b, &c, &[0.5, 0.25, 0.25]), Some(Sign::Zero));
/// assert_eq!(orient3d(&a, &b, &c, &[f64::NAN, 0.0, 0.0]), None);
/// ```
#[inline]
pub fn orient3d(a: &[f64; 3], b: &[f64; 3], c: &[f64; 3], d: &[f64; 3]) -> Option<Sign> {
    generated::orient3d::staged([a, b, c, d])
}

/// The individual stages of each predicate, for tests and benchmarks.
#[doc(hidden)]
pub mod stages {
    pub use crate::generated::orient3d;
}