Controlled perturbation of sets of line segments in \(\mathbb R^2\) with smart processing order (Q543787)

A controlled perturbation scheme for approximation of a set of line segments in the plane with fixed-precision number types is presented. The controlled perturbation scheme is based on an incremental perturbation of the line segment endpoints to eliminate potential degeneracies. First, the main idea and the suggested algorithm is presented. Then, the considered potential degeneracy cases are discussed and an upper bound of the perturbation magnitudes is derived. Next, sorting algorithms applied to the order determination of the processed endpoints are introduced and their modification for using in the suggested controlled perturbation scheme is described. Finally, experimental results obtained by the implemented algorithm are given and a significant decreasing in the perturbation magnitude in many cases is shown.