Re: [gsoc20]Proposal for general robust predicates for Boost.Geometry

From: Tinko Bartels (tinkobartels_at_[hidden])
Date: 2020-03-30 12:12:36

Hello,
Thanks to everybody who gave me feedback for my proposal and thanks for the
pointers to further literature. With the end of the application period
approaching, I've made a final update to the proposal and the proof of
concept. Because this may help clarify what I exactly propose, I'll share
the update and a minimal example in this thread:

The proposal is for a library that automates the creation of adaptive
predicates. Consider the orient2d-predicate which evaluates:

sign( (a[0] - c[0]) * (b[1] - c[1]) - (a[1] - c[1]) * (b[0] - c[0]) )

Right now, Boost.Geometry has, in the extensions, a robust, adaptive
implementation of this predicate:
https://github.com/boostorg/geometry/blob/2dbe5bf554190075ba2e51a9e067a8da520fff71/include/boost/geometry/extensions/triangulation/strategies/cartesian/detail/precise_math.hpp#L288
.

I propose to create such predicates for arbitrary polynomial expressions
automatically. What is achieved in the function orient2d using manual error
analysis and careful manual implementation, can then instead be achieved by

#include "static_exact.h"
...
using A = float_wrapper<double>;
auto det = ((A(a0) + A(-c0)) * (A(b1) + A(-c1))
        + (A(-a1) + A(c1)) * (A(b0) + A(-c0))).sign();
...

The updated proof of concept can be found at
https://github.com/tinko92/expansion_math . It has all the features that are
necessary for the orient2d example shown here. Note that in this
proof-of-concept-stage, it is not yet as adaptive as the full
implementation, but the most important approximation step is included. The
performance measures in my updated proposal demonstrate that the performance
is comparable to the manual implementation. Checking the assembly, I was
able to verify that the automatically computed error bound matches the
manually computed error bound that can be found in the earlier
implementation.

Kind regards
Tinko Bartels

--
Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html