gerobust — Robust Geometry
Python extension of the C implementation of robust and quick incircles tests, produced by Janathan Richard Shewchuk and explained in its paper Robust Adaptive Floating-Point Geometric Predicates.
(see more in tests)
from gerobust.predicates import clockwise, counter_clockwise, incircle triangle = (0, 0), (0, 1), (1, 0) print(clockwise(*triangle)) # True print(counter_clockwise.fast(*triangle)) # False print(incircle(*triangle, (1, 1))) # False print(incircle(*triangle, (1, 1), strict=False)) # True
pip install gerobust
git clone firstname.lastname@example.org:Aluriak/gerobust.git cd gerobust make tests
Floating-point and compiler
The technics used in the C code needs the compiler to work with the IEEE 754 floating-point standard.
By looking about it in the web, i found the gcc wiki
that seems to get its full support (without micro optimization that could kill the C implementation)
-frounding-math -fsignaling-nans options or the
#pragma STDC FENV ACCESS ON pragma.
The former is used. I however expect that only gcc is handled with this library. IEEE 754 compliancy through a standard way should be a short-term goal.
Patches as PR and ideas as issues are welcome.
Few ways to improve this lib :
- more geometric applications of the global method, for a more complete library
- compatibility with others compiler/OS
- unit test showing the (¬)robustness of functions
- general improvements over the python codebase (organization, style, efficiency, doc)
Abstract and citation reproduced below.
Robust Adaptive Floating-Point Geometric Predicates Jonathan Richard Shewchuk School of Computer Science Carnegie Mellon University Pittsburgh, Pennsylvania 15213 Fast C implementations of four geometric predicates, the 2D and 3D orientation and incircle tests, are publicly available. Their inputs are ordinary single or double precision floating-point numbers. They owe their speed to two features. First, they employ new fast algorithms for arbitrary precision arithmetic that have a strong advantage over other software techniques in computations that manipulate values of extended but small precision. Second, they are adaptive; their running time depends on the degree of uncertainty of the result, and is usually small. These algorithms work on computers whose floating-point arithmetic uses radix two and exact rounding, including machines that comply with the IEEE 754 floating-point standard. Timings of the predicates, in isolation and embedded in 2D and 3D Delaunay triangulation programs, verify their effectiveness. Proceedings of the Twelfth Annual Symposium on Computational Geometry (Philadelphia, Pennsylvania), pages 141-150, ACM, May 1996. PostScript (310k). Paper available through the URL http://www.cs.berkeley.edu/~jrs/papers/robust-predicates.ps For additional details and associated software, see the Web page http://www.cs.cmu.edu/~quake/robust.html