Constructions géométriques à précision fixée
Philippe Guigue · HAL (Le Centre pour la Communication Scientifique Directe) · 2003
Robustness problems resulting from the substitution of floating-point arithmetic for exact arithmetic on real numbers are often an obstacle to the practical implementation of geometric algorithms. For algorithms that are purely combinatorial, the use of the exact computation paradigm gives a satisfactory solution to this problem. However, this paradigm does not allow to practically solve the case of algorithms that reuse or cascade the construction of new geometric objects. This thesis treats the problem of rounding the result of set operations on polygonal regions onto the integer grid. We propose several rounding modes that allow to guarantee some interesting metric and topological properties between the exact result and its rounded counterpart such as inclusion properties and convexity preservation. Our methods are based on the rounding of elementary geometric constructions, e.g. rounding a vertex of a convex polygon to its nearest interior grid point, for which we propose efficient algorithms. We finally present some fast overlap tests that allow to detect in a robust manner the intersection of several kinds of convex objects in the plane and in the three dimensional space. All methods have a direct application in domains such as CAD and computer graphics.