# implicit-predicates
Exact geometric predicates in Rust for explicit points and for *implicit*
points: points defined by an unevaluated construction, such as a point on an
edge or inside a triangle.
> **Status: early development.** Today the crate provides `orient3d` for
> explicit points and points on a segment; the API may change. `insphere`
> and the other kinds of implicit points do not exist yet.
## Example
```rust
use implicit_predicates::{Lnc, 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));
// A point on the edge between b and c, c + 0.3 (b - c): on the plane,
// exactly, although its coordinates are not representable as `f64`.
let m = Lnc::new(b, c, 0.3).unwrap();
assert_eq!(orient3d(&a, &b, &c, &m), Some(Sign::Zero));
```
`orient3d` takes four points of any type that implements `Point`, and
returns the exact sign of the determinant of `a - d`, `b - d`, `c - d`
(Shewchuk's convention) at their exact coordinates. The point types are
`[f64; 3]` (an explicit point, not validated), `Explicit` (a validated
explicit point), `Lnc`, built from two explicit points `p` and `q` and a
parameter `t` in `[0, 1]`, the point `q + t (p - q)` on the segment between
them, and `AnyPoint`, either of the last two.
A floating-point filter on the approximations of the points decides most
calls. When it cannot, explicit points go to exact stages on floating-point
expansions held on the stack, so no call on explicit points allocates. With
a point on a segment, the exact coordinates of the points go to an arena of the
calling thread, 16,384 `f64` to start with, that grows on the heap when a
call needs more. `orient3d_in` takes the arena instead. Without its default
`std` feature the crate is `no_std`, and `orient3d_in` takes the place of
`orient3d`.
The result is an `Option<Sign>`, provisionally. It is `None` when an input of
a point is not finite. Otherwise, only if the earlier stages cannot decide
either: for explicit points, when a nonzero coordinate has a magnitude
outside `2^-188..=2^239` (about `2.5e-57` to `8.8e71`); with a point on a
segment, when the inputs of a point are beyond the range of its own exact
arithmetic, or a nonzero component of the exact coordinates has a magnitude
outside `2^-188..=2^235`. The documentation of `orient3d` gives a condition
on the inputs of an `Lnc` under which the call is always decided, such as
coordinates between `2^-30` and `2^233` with `t` zero or at least `2^-54`.
A later version will decide every finite input.
`Point` is a public trait, and a type of your own can implement it. The
predicates rely on its contract without checking it: `err` bounds the error
of each coordinate of `approx`, `is_explicit` returns `true` only when
`approx` holds the exact coordinates with zero error, and `exact` writes
valid expansions. An implementation that breaks it makes the predicates
return wrong signs, silently. The predicates support only exact coordinates
with a weight of `Weight::One` for now: a point whose `exact` gives another
weight makes them return `None`. The point types of this crate are generated by
`implicit-predicates-gen` from their declarations.
## Goals
- Exact sign for every finite input (not yet reached by `orient3d`: see
above).
- Speed close to classical filtered predicates in the common case.
- Explicit points and implicit points through one API.
- New predicates and point types through a code generator.
Planned for the first release: `orient3d`, `insphere` and a symbolically
perturbed `insphere`, over explicit points and points on a segment. Only
`orient3d` exists today.
## Minimum supported Rust version
Rust 1.86.
## License
Licensed under either of Apache License, Version 2.0 or MIT license, at your
option.