Skip to main content

Extension in C for incircles tests (2D/3D)

Project description

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.

usage example

(see more in tests)

from gerobust.predicates import clockwise, counter_clockwise, incircle

triangle = (0, 0), (0, 1), (1, 0)

print(clockwise(*triangle))  # True
print(*triangle))  # False
print(incircle(*triangle, (1, 1)))  # False
print(incircle(*triangle, (1, 1), strict=False))  # True


pip install gerobust


git clone
cd gerobust
make tests


github and pypi

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) with the -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

For additional details and associated software, see the Web page

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

gerobust-0.4.1.tar.gz (44.5 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page