Crate geometry_predicates[−][src]

A safe Rust port of the robust adaptive floating-point geometric predicates.

This crate provides a Rust solution to efficient exact geometry predicates used widely for computational geometry.

In addition, the building blocks of these predicates, namely the adaptive precision floating-point arithmetic primitives, are also exposed in predicates to allow for extensions to other predicates or exact geometric constructions.

Background

These predicates have been a staple in computational geometry for many years now and are widely used in industry. In the context of geometry algorithms, it is often essential to determine the orientation of a point with respect to a line (or a plane) and whether a point lies inside a circle (or a sphere) or not. The reason why these tests often need to be exact is because many geometry algorithms ask questions (to determine orientation or in-circle/sphere) about point configurations that require consistent answers. For instance, if a, b, and c are three points on a 2D plane, to ask where b with respect to the line through a and c (left-of, right-of, or coincident) is the same as asking where a lies with respect to the line through c and b. In Rust, this condition can be written as

assert_eq!(orient2d(a,c,b).signum(), orient2d(c,b,a).signum());

Mathematically, predicates like orient2d are defined as

                                        ⎛⎡ax ay 1⎤⎞
orient2d([ax,ay],[bx,by],[cx,cy]) := det⎜⎢bx by 1⎥⎟
                                        ⎝⎣cx cy 1⎦⎠

It's easy to see that these predicates solve the problem of computing the determinant of small matrices with the correct sign, regardless of how close the matrix is to being singular.

For instance to compute the determinant of a matrix [a b; c d] with the correct sign, we can invoke

assert_eq!(orient2d([a,b], [c,d], [0.0,0.0]), a*d - b*c);

For more details please refer to the original webpage for these predicates.

Caveats

These predicates do NOT handle exponent overflow [1], which means inputs with floats smaller than 1e-142 or larger than 1e201 may not produce accurate results. This is true for the original predicates in predicates.c as well as other Rust ports and bindings for these predicates.

References

[1] Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete & Computational Geometry 18(3):305–363, October 1997.
[2] Robust Adaptive Floating-Point Geometric Predicates Proceedings of the Twelfth Annual, Symposium on Computational Geometry (Philadelphia, Pennsylvania), pages 141–150, Association for Computing Machinery, May 1996

Re-exports

pub use predicates::incircle;

pub use predicates::incircle_fast;

pub use predicates::insphere;

pub use predicates::insphere_fast;

pub use predicates::orient2d;

pub use predicates::orient2d_fast;

pub use predicates::orient3d;

pub use predicates::orient3d_fast;

Modules

predicates