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

From: Tinko Bartels (tinkobartels_at_[hidden])
Date: 2020-03-24 00:13:14

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