[gsoc20]Proposal for general robust predicates for Boost.Geometry
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/19zH9QuSSNWAHm1DP5poxbRxcMXlzRVWfL5WslbeS... Kind regards Tinko Bartels -- Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html
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
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
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
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/2dbe5bf554190075ba2e51a9e067a8da52... . 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
participants (3)
-
Christopher Kormanyos -
Marc Glisse -
Tinko Bartels