{ } JustinGeoSci

Geometric predicates

The four predicates: each returns the exact sign of a determinant of its input points, for every finite input.

2D predicates

Orientation and in-circle tests on [f64; 2] points. Both are called from the crate root, arithmetica::orient2d and arithmetica::incircle.

orient2d

pub fn orient2d(pa: [f64; 2], pb: [f64; 2], pc: [f64; 2]) -> Result<Sign, NonFinite>

Orientation of three points in the plane: Positive if pa → pb → pc turns counterclockwise (with the y-axis up), Negative if clockwise, Zero if the three points are collinear. Equivalently, the side of the directed line pa → pb on which pc lies: left is Positive.

Orientation determinant\det\begin{pmatrix} a_x-c_x & a_y-c_y \\ b_x-c_x & b_y-c_y \end{pmatrix}

Errors: Err(NonFinite) if any input coordinate is NaN or infinite. For every finite input the result is Ok with the exact sign.

use arithmetica::{Sign, orient2d};

assert_eq!(orient2d([0.0, 0.0], [1.0, 0.0], [0.0, 1.0]), Ok(Sign::Positive)); // counterclockwise
assert_eq!(orient2d([0.0, 0.0], [0.0, 1.0], [1.0, 0.0]), Ok(Sign::Negative)); // clockwise
assert_eq!(orient2d([0.0, 0.0], [1.0, 1.0], [2.0, 2.0]), Ok(Sign::Zero));     // collinear

// Collinear even though no coordinate is a "round" number:
// 1/3, 2/3 and 1/7 each round to some f64, and the three rounded
// points still lie exactly on y = x.
let (a, b, c) = ([1.0 / 3.0, 1.0 / 3.0], [2.0 / 3.0, 2.0 / 3.0], [1.0 / 7.0, 1.0 / 7.0]);
assert_eq!(orient2d(a, b, c), Ok(Sign::Zero));

incircle

pub fn incircle(pa: [f64; 2], pb: [f64; 2], pc: [f64; 2], pd: [f64; 2]) -> Result<Sign, NonFinite>

Whether pd lies inside the circle through pa, pb and pc. With the three points in counterclockwise order, the result is Positive inside, Negative outside and Zero on the circle; clockwise order reverses the sign. This is the Delaunay test.

Lifted determinant\det\begin{pmatrix} a_x-d_x & a_y-d_y & (a_x-d_x)^2+(a_y-d_y)^2 \\ b_x-d_x & b_y-d_y & (b_x-d_x)^2+(b_y-d_y)^2 \\ c_x-d_x & c_y-d_y & (c_x-d_x)^2+(c_y-d_y)^2 \end{pmatrix}

Errors: Err(NonFinite) if any input coordinate is NaN or infinite. For every finite input the result is Ok with the exact sign.

use arithmetica::{Sign, incircle};

// The circle through (0, 0), (2, 0) and (0, 2) has center (1, 1)
// and passes through (2, 2).
let (a, b, c) = ([0.0, 0.0], [2.0, 0.0], [0.0, 2.0]);
assert_eq!(incircle(a, b, c, [1.0, 1.0]), Ok(Sign::Positive)); // inside
assert_eq!(incircle(a, b, c, [3.0, 3.0]), Ok(Sign::Negative)); // outside
assert_eq!(incircle(a, b, c, [2.0, 2.0]), Ok(Sign::Zero));     // on the circle

// Listing the three points clockwise reverses the sign.
assert_eq!(incircle(a, c, b, [1.0, 1.0]), Ok(Sign::Negative));

3D predicates

Orientation and in-sphere tests on [f64; 3] points, called as arithmetica::orient3d and arithmetica::insphere.

orient3d

pub fn orient3d(pa: [f64; 3], pb: [f64; 3], pc: [f64; 3], pd: [f64; 3]) -> Result<Sign, NonFinite>

Orientation of four points in space: Positive if pd lies below the plane through pa, pb and pc, where those three appear counterclockwise when seen from above; Negative if above; Zero if the four points are coplanar. The value is six times the signed volume of the tetrahedron.

Orientation determinant\det\begin{pmatrix} 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 \end{pmatrix}

Errors: Err(NonFinite) if any input coordinate is NaN or infinite. For every finite input the result is Ok with the exact sign.

use arithmetica::{Sign, orient3d};

// pa, pb, pc lie in the plane z = 0 and appear counterclockwise from above.
let (a, b, c) = ([0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]);
assert_eq!(orient3d(a, b, c, [0.0, 0.0, -1.0]), Ok(Sign::Positive)); // below the plane
assert_eq!(orient3d(a, b, c, [0.0, 0.0, 1.0]), Ok(Sign::Negative));  // above the plane
assert_eq!(orient3d(a, b, c, [1.0, 1.0, 0.0]), Ok(Sign::Zero));      // coplanar

insphere

pub fn insphere(pa: [f64; 3], pb: [f64; 3], pc: [f64; 3], pd: [f64; 3], pe: [f64; 3]) -> Result<Sign, NonFinite>

Whether pe lies inside the sphere through pa, pb, pc and pd. When orient3d(pa, pb, pc, pd) is Positive, the result is Positive inside, Negative outside and Zero on the sphere; the opposite orientation reverses the sign. The result is also Zero if the four reference points are coplanar. This is the 3D Delaunay test.

Lifted determinant\det\begin{pmatrix} a_x-e_x & a_y-e_y & a_z-e_z & \lVert a-e\rVert^2 \\ b_x-e_x & b_y-e_y & b_z-e_z & \lVert b-e\rVert^2 \\ c_x-e_x & c_y-e_y & c_z-e_z & \lVert c-e\rVert^2 \\ d_x-e_x & d_y-e_y & d_z-e_z & \lVert d-e\rVert^2 \end{pmatrix}

Errors: Err(NonFinite) if any input coordinate is NaN or infinite. For every finite input the result is Ok with the exact sign.

use arithmetica::{Sign, insphere, orient3d};

// A positively oriented tetrahedron. Its circumsphere has center
// (0.5, 0.5, -0.5) and squared radius 0.75.
let (a, b, c, d) = ([0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, -1.0]);
assert_eq!(orient3d(a, b, c, d), Ok(Sign::Positive));

assert_eq!(insphere(a, b, c, d, [0.5, 0.5, -0.5]), Ok(Sign::Positive)); // inside
assert_eq!(insphere(a, b, c, d, [2.0, 2.0, 2.0]), Ok(Sign::Negative));  // outside
assert_eq!(insphere(a, b, c, d, [1.0, 1.0, 0.0]), Ok(Sign::Zero));      // on the sphere