Fast robust predicates for computational geometry in JavaScript. Provides reliable 2D and 3D point orientation tests (orient2d
, orient3d
, incircle
, insphere
) that are not susceptible to floating point errors (without sacrificing performance). A modern port of Jonathan R Shewchuk's C code, an industry standard since 1996.
Figure: non-robust vs robust orient2d
test for points within a tiny range (2-42).
Note: unlike J. Shewchuk's original code, all the functions in this library assume y
axis is oriented downwards ↓, so the semantics are different.
- Returns a positive value if the points
a
,b
, andc
occur in counterclockwise order (c
lies to the left of the directed line defined by pointsa
andb
). - Returns a negative value if they occur in clockwise order (
c
lies to the right of the directed lineab
). - Returns zero if they are collinear.
The result is also an approximation of twice the signed area of the triangle defined by the three points.
- Returns a positive value if the point
d
lies outside the circle passing througha
,b
, andc
. - Returns a negative value if it lies inside.
- Returns zero if the four points are cocircular.
The points a
, b
, and c
must be in counterclockwise order, or the sign of the result will be reversed.
- Returns a positive value if the point
d
lies above the plane passing througha
,b
, andc
, meaning thata
,b
, andc
appear in counterclockwise order when viewed fromd
. - Returns a negative value if
d
lies below the plane. - Returns zero if the points are coplanar.
The result is also an approximation of six times the signed volume of the tetrahedron defined by the four points.
- Returns a positive value if the point
e
lies outside the sphere passing througha
,b
,c
, andd
. - Returns a negative value if it lies inside.
- Returns zero if the five points are cospherical.
The points a
, b
, c
, and d
must be ordered so that they have a positive orientation
(as defined by orient3d
), or the sign of the result will be reversed.
Simple, approximate, non-robust versions of predicates above. Use when robustness isn't needed.
import {orient2d} from 'robust-predicates';
const ccw = orient2d(ax, ay, bx, by, cx, cy) > 0;
Install with npm install robust-predicates
or yarn add robust-predicates
, or use one of the browser builds:
- predicates.min.js (all predicates)
- orient2d.min.js (
orient2d
,orient2dfast
) - orient3d.min.js (
orient3d
,orient3dfast
) - incircle.min.js (
incircle
,incirclefast
) - insphere.min.js (
insphere
,inspherefast
)
This project is just a port — all the brilliant, hard work was done by Jonathan Richard Shewchuk.
The port was also inspired by Mikola Lysenko's excellent Robust Arithmetic Notes and related projects like robust-orientation and robust-in-sphere.
Since the original code is in the public domain, this project follows the same choice. See Unlicense.