Crate robust

source ·
Expand description

Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry

This is a direct transcript of the source code and algorithms provided by Jonathan Richard Shewchuk (https://www.cs.cmu.edu/~quake/robust.html) See the paper and the source code for more information.

The module offers adaptive and precise calculations for orientation queries – “on which side of a line (2d) or plane (3d) does a point lie?” – and in-circle / in-sphere queries – “is a given point contained in the circumference of a triangle?”.
The “adaptive” nature will increase performance only if a simpler calculation cannot be guaranteed to be accurate enough, yielding higher performance on average.

The public API will accept both f32 and f64 input points for predicate checking, with input being converted to f64 values for internal use. This has no effect on precision, as the IEEE-754 standard (section 5.3) guarantees that conversion from f32 to f64 must be exact.

Features

  • no_std: Build without the Rust standard library

Structs

  • A two dimensional coordinate.
  • A three dimensional coordinate.

Functions

  • Returns a positive value if the coordinate pd lies inside the circle passing through pa, pb, and pc.
    Returns a negative value if it lies outside the circle.
    Returns 0 if the four points are cocircular.
    Note: The points pa, pb, and pc must be in counterclockwise order, or the sign of the result will be reversed.
  • Returns a positive value if the point pe lies inside the sphere passing through pa, pb, pc, and pd.
    Returns a negative value if it lies outside.
    Returns 0 if the five points are cospherical.
    NOTE: The points pa, pb, pc, and pd must be ordered so that they have a positive orientation.
  • Returns a positive value if the coordinates pa, pb, and pc occur in counterclockwise order (pc lies to the left of the directed line defined by coordinates pa and pb).
    Returns a negative value if they occur in clockwise order (pc lies to the right of the directed line pa, pb).
    Returns 0 if they are collinear.
  • Returns a positive value if the point pd lies below the plane passing through pa, pb, and pc (“below” is defined so that pa, pb, and pc appear in counterclockwise order when viewed from above the plane).
    Returns a negative value if pd lies above the plane.
    Returns 0 if they are coplanar.