gerobust 0.4.1
Extension in C for incircles tests (2D/3D)
Keywords: C function robust geometry

# gerobust — Robust Geometry
Python extension of the C implementation of robust and quick incircles tests,
produced by [Janathan Richard Shewchuk](https://www.cs.cmu.edu/~quake/robust.html) and explained in its paper *Robust Adaptive Floating-Point Geometric Predicates*.

## usage example
(see more in [tests](test/))

    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


## installation

    pip install gerobust

### Tests

    git clone git@github.com:Aluriak/gerobust.git
    cd gerobust
    make tests

## links
[github](http://github.com/aluriak/gerobust) and [pypi](http://pypi.python.org/pypi/gerobust)


## 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](https://gcc.gnu.org/wiki/FloatingPointMath)
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](gerobust/build_geolib.py#L33). I however expect that only gcc is handled with this library. IEEE 754 compliancy through a standard way should be a short-term goal.

## Contributions
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)


## Bibliography
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