3 ms·
Does anyone know how this library maintains geometric robustness in the face of rounding errors? E.g. if you rotate a unit square by 45 degrees (giving irration
by amelius 4y ago
Does anyone know how this library maintains geometric robustness in the face of rounding errors? E.g. if you rotate a unit square by 45 degrees (giving irrational coordinates), then rotate it back and subtract it from the original, you are left with exactly nothing?
- everybodyknows 4y agoExactness of results is not listed among its design principles: https://brunolevy.github.io/geogram/geogram_design.html https://brunolevy.github.io/geogram/geogram_design.html CGAL offers exact algorithms: https://doc.cgal.org/latest/Kernel_23/index.html#Chapter_2D_and_3D_Geometry_Kernel https://doc.cgal.org/latest/Kernel_23/index.html#Chapter_2D_...
- BrunoLevy01 4y agoExactness is not "advertized" on the main page or as a "design principle" but it is there ! Geogram uses "arithmetic expansions", arrays of floating point numbers that can represent numbers with arbitrary precision while being reasonably performant (it is the same thing used by Jonathan Shewchuk in his predicates). In addition, besides predicates, Geogram can use arithmetic expansions to represent intermediary results of computation (I'm currently developing boolean operations that extensively make use of this feature).
- BrunoLevy01 4y agoGeogram uses arithmetic expansions and filtered predicates, as explained in the following publication: https://hal.inria.fr/hal-01225202 https://hal.inria.fr/hal-01225202