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

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Boost - Dev mailing list
Hello Boost-Community,

I have prepared a draft proposal for general robust predicates for
Boost.Geometry.

The ideas are described in more detail in the proposal, but I will briefly
describe them here:

A number of geometric algorithms, such as the triangulation of a point set,
employ geometric predicates (implemented as strategies in Boost.Geometry).
One example for such a predicate is the 2d orientation test, which, given
three points p1, p2, p3, determines whether p3 lies on the left or right
side of the line segment that goes through p1 and p2.

Using floating-point arithmetics to answer that question can lead to
incorrect and ultimately inconsistent results that may cause the algorithm
that employs the predicate to produce nonsensical results or crash entirely
for certain inputs.

Using algorithms for exact floating-point arithmetics combined with some
considerations regarding forward error analysis, a complicated method can be
implemented that evaluates such predicates robustly and only adaptively
increases the precision if necessary to avoid expensive high precision
computations whenever possible.

I propose a general, automated approach that generates such robust, adaptive
predicates from arbitrary arithmetic expressions. Currently, Boost.Geometry
has robust adaptive predicates for the 2d orientation and the 2d incircle
test. This work would enable us to easily extend this to 3d orientation, 3d
insphere, and generally all predicates that can be evaluated by determining
the sign of a polynomial.

I want to present my proposal for review publicly now:

https://docs.google.com/document/d/19zH9QuSSNWAHm1DP5poxbRxcMXlzRVWfL5WslbeSB38/edit?usp=sharing

Kind regards
Tinko Bartels



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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

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

Boost - Dev mailing list
On Mon, 23 Mar 2020, Tinko Bartels via Boost wrote:

> I have prepared a draft proposal for general robust predicates for
> Boost.Geometry.

Hello,

some references that can be relevant:

https://hal.inria.fr/inria-00344297

http://alice.loria.fr/index.php/software/4-library/75-geogram.html
(BSD license)

All the parts of CGAL relevant to your project are LGPL, I believe. I.e.
predicates are LGPL, while the triangulation datastructure and algorithm
are GPL.

--
Marc Glisse

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

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

Boost - Dev mailing list
 > I have prepared a draft proposal for general robust> predicates for Boost.Geometry.
I believe this is a very good proposal. I especiallyappreciate the theoretical background is rich and detailed.
I left two anonymous trivial spelling suggestions notedat the document.
Good luck and kind regards, Chris


    On Tuesday, March 24, 2020, 2:24:43 PM GMT+1, Marc Glisse via Boost <[hidden email]> wrote:  
 
 On Mon, 23 Mar 2020, Tinko Bartels via Boost wrote:

> I have prepared a draft proposal for general robust predicates for
> Boost.Geometry.

Hello,

some references that can be relevant:

https://hal.inria.fr/inria-00344297

http://alice.loria.fr/index.php/software/4-library/75-geogram.html
(BSD license)

All the parts of CGAL relevant to your project are LGPL, I believe. I.e.
predicates are LGPL, while the triangulation datastructure and algorithm
are GPL.

--
Marc Glisse

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
 

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

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

Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost