Dynamic computation of a line segment arrangement using finite precision

Abstract

The present invention produces a data structure that indicates a partition of a given input set of line segments in a plane using a technique that is mathematically robust, canonical and dynamic. The technique is robust because it assumes a finite precision model of computer arithmetic and rounds the endpoints and intersections of all line segments to representable points in a way that is globally topologically consistent with the input set of line segments and that keeps the position of each rounded line segment close to the position of the input segment. The technique is canonical because the output partition produced is a function of the set of segments currently present only, and not of the history of insertion and deletions. This canonical aspect of the technique is facilitated by storing the input unrounded line segments in the partition data structure so that they are associated with their rounded fragments. The technique is dynamic because input unrounded line segments may be incrementally added to and deleted from the data structure representation of the partition without recomputing the entire partition for each change. An illustrated implementation of the technique uses a randomized incremental approach that produces a partition having the form of a vertical cell decomposition.