Crate implicit_predicates 

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 one predicate, orient3d, over points of any type that implements Point: an approximation of its coordinates, a bound on the error of each one, and its exact coordinates. The point types of the crate are [f64; 3], an explicit point that is not validated; Explicit, a validated explicit point; Lnc, a point on the segment between two explicit points; and AnyPoint, either of the last two. Like every predicate of the crate, orient3d 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. The point types are generated from their declarations in the same way. A type of your own can implement Point too, but the predicates rely on its contract without checking it: an implementation that breaks it makes them return wrong signs. insphere and the other kinds of implicit points do not exist yet.

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.
let m = Lnc::new(b, c, 0.3)?;
assert_eq!(orient3d(&a, &b, &c, &m), Some(Sign::Zero));

A point of type Lnc is q + t (p - q); its error bound is zero on the coordinates that are exact, here those that p and q share:

use implicit_predicates::{Lnc, Point};

let m = Lnc::new([0.3, 2.0, 5.0], [0.1, 2.0, 5.0], 0.5)?;
assert!(m.err()[0] > 0.0);
assert_eq!(&m.approx()[1..], &[2.0, 5.0]);
assert_eq!(&m.err()[1..], &[0.0, 0.0]);

Features

• std, on by default: orient3d, which keeps the exact coordinates of implicit points in an arena of each thread. Without it the crate is no_std, and orient3d_in, which takes the arena, is the way to call the predicate.

Structs

ExactCoords

The exact coordinates of a point, in homogeneous form: the point is (x / w, y / w, z / w). The spans belong to the arena given to Point::exact, and each holds a valid expansion (see expansion); the predicates that read them do not check it.

Explicit

A point of type Explicit: the point with the coordinates p, given exactly. Its approximation is its coordinates and its error is zero.

Lnc

A point of type Lnc, computed from p, q and t:

Scratch

A bump arena of f64 components for expansion arithmetic. See the module documentation for the model.

ScratchExhausted

The error of a Scratch operation whose worst-case result does not fit in the free part of the arena.

Enums

AnyPoint

A point of any of the types of this module.

ExactError

The error of Point::exact.

PointError

Why the constructor of a point type rejected its inputs.

Sign

The sign of a real quantity.

Weight

The common denominator of the exact coordinates of a point.

Traits

Point

A point in three dimensions, as the predicates read it.

Functions

orient3d

The orientation of d with respect to the plane through a, b and c: the exact sign of the determinant

orient3d_in

orient3d with the arena scratch for the exact coordinates of implicit points, instead of the arena of the thread: the same result, or an error if scratch runs out of room. Available without std.