Dynamic computation of a line segment arrangement using finite precision arithmetic for use in a processor controlled system

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.

What is claimed: 
     
       1. For a processor-controlled system capable of operating on and displaying arrangements of line segments in a plane, a method for dynamically producing an output partition data structure representing said arrangement of line segments, said output partition data structure induced by an input unrounded line segment; the input unrounded line segment being represented by a set of real coordinates in the plane, the output partition data structure indicating an output rounded line segment representing the input line segment by a set of finite precision coordinates; the method comprising: receiving data indicating the an input unrounded line segment and a signal to insert the unrounded input line segment into an input partition data structure indicating a first partition of the plane;   accessing the input partition data structure; the input partition data structure including data indicating a prior set of unrounded line segments; the prior set of unrounded line segments including a boundary set of unrounded line segments forming a rectangular boundary lying on the plane; locations in the input partition data structure being capable of being specified with reference to a finite precision grid of tiles superimposed on the plane; each tile having a position included therein referred to as an integral point having finite precision coordinates; the input unrounded line segment having real coordinates specifying a position within the rectangular boundary;   determining a plurality of tiles in the finite precision grid related to the input unrounded line segment using the prior set of unrounded line segments; the plurality of tiles in the finite precision grid related to the input unrounded line segment being hereafter referred to as a plurality of   related hot pixels; each related hot pixel including an endpoint of the input unrounded line segment or at least one point on an unrounded line segment included in the input partition data structure,   for each related hot pixel. performing a rounding operation using the input unrounded line segment; the rounding operation replacing real coordinates of a nonintegral point on an unrounded line segment located within the boundary of the related hot pixel with the finite precision coordinates of the integral point of the related hot pixel; the rounding operation causing an unrounded line segment to be split into two fragment line segments, each referred to individually as a fragment and collectively as a polysegment, having a vertex at the integral point in the related hot pixel; each fragment produced by the rounding operation being referred to as belonging to the unrounded line segment from which it was produced;   adding the fragments of the polysegment to the input partition data structure to produce an updated output partition data structure;   storing the input unrounded line segment in the output partition data structure; the input unrounded line segment being associated in the output partition data structure with all of the fragments belonging to the unrounded line segment from which it was produced; and   displaying an arrangement of line segments using said output partition data structure.   
     
     
       2. The method of claim 1 for operating a processor-controlled machine to dynamically produce an output partition data structure further including receiving a second input unrounded line segment and a signal to delete the second unrounded input line segment from the input partition data structure;   determining at least one fragment belonging to the input unrounded line segment; and   deleting the determined at least one fragment belonging to the input unrounded line segment from the input partition data structure to produce the updated output partition data structure.   
     
     
       3. The method of claim 1 for operating a processor-controlled machine to dynamically produce an output partition data structure wherein the rounding operation has a characteristic property that a partition of the plane induced by at least two intersecting polysegments produced by performing the rounding operation on the input unrounded line segment is topologically consistent with and geometrically accurate with respect to a partition of the plane induced by at least two intersecting input unrounded line segments from which the two intersecting polysegments were produced. 
     
     
       4. The method of claim 1 for operating a processor-controlled machine to dynamically produce an output partition data structure wherein determining the related hot pixels using the prior set of unrounded line segments includes locating first and second hot pixels respectively containing endpoints of the input unrounded line segment; the first and second hot pixels being referred to as new hot pixels. 
     
     
       5. The method of claim 4 wherein determining the related hot pixels using the prior set of unrounded line segments further includes locating an intersection hot pixel including a vertex indicating an intersection between the input unrounded line segment and at least one unrounded line segment included in the prior set of unrounded line segments; the intersection hot pixel being referred to as a new hot pixel. 
     
     
       6. The method of claim 5 wherein determining the related hot pixels using the prior set of unrounded line segments further includes determining an unrounded line segment included in the prior set of unrounded line segments having a portion thereof passing through a new hot pixel. 
     
     
       7. The method of claim 1 for operating a processor-controlled machine to dynamically produce an output partition data structure wherein determining the related hot pixels using the prior set of unrounded line segments further includes locating a prior-designated hot pixel containing at least one point on the input unrounded line segment. 
     
     
       8. The method of claim 1 for operating a processor-controlled machine to dynamically produce an output partition data structure wherein all regions in the plane indicated by the input and output partition data structures include subregions referred to as cells; the cells having a standardized geometric shape having a fixed number of bounded sides; the method further including, when adding the determined at least one fragment representing the unrounded line segment to the input partition data structure produces a region in the plane having a shape different from the standardized geometric shape, adding line segments referred to as attachments to the input partition data structure to produce at least one cell having a standardized geometric shape. 
     
     
       9. The method of claim 8 wherein the standardized geometric shape is a trapezoid having at least two parallel sides; the line segments being added extending vertically from a vertex of a fragment produced by adding the unrounded line segment; the partition of the plane being referred to as a trapezoidal decomposition. 
     
     
       10. The method of claim 1 for operating a processor-controlled machine to dynamically produce an output partition data structure wherein the rounding operation replaces the real coordinates of a nonintegral point on an unrounded line segment located within the boundary of a related hot pixel with the finite precision coordinates of the integral point of the related hot pixel according to a set of rounding rules; replacing the real coordinates with the finite precision coordinates being referred to as perturbing the unrounded line segment to the integral point of a related hot pixel; the set of rules including perturbing an endpoint of the input unrounded line segment located within the boundary of a related hot pixel to the integral point of the related hot pixel; and   perturbing an intersection point of the input unrounded line segment with an unrounded line segment included in the prior set of unrounded line segments located within the boundary of a related hot pixel to the integral point of the related hot pixel.   
     
     
       11. The method of claim 10 wherein the set of rules further includes perturbing an unrounded line segment included in the prior set of unrounded line segments located within the boundary of a related hot pixel to the integral point of the related hot pixel. 
     
     
       12. The method of claim 1 wherein the tile in the finite precision grid of tiles superimposed on the plane has the shape of a unit square. 
     
     
       13. An article of manufacture for use by a processor-controlled system capable of operating on and displaying arrangements of line segments in a plane, the system including input signal circuitry for receiving input signals; storage medium access circuitry for accessing a medium that stores data; a memory device for storing a partition data structure representing an arrangement of line segments in a plane; and a processor connected for receiving the input signals from the input signal circuitry, connected for accessing the partition data structure stored in the memory device, and connected for receiving data from the storage medium access circuitry; the article comprising: a data storage medium that can be accessed by the storage medium access circuitry when the article is used by the machine; and   data stored in the data storage medium so that the storage medium access circuitry can provide the stored data to the processor when the article is used by the machine; the stored data comprising instruction data indicating instructions the processor can execute, said instruction data including instructions for: receiving data from the input signal circuitry indicating an input unrounded line segment and a signal to insert the unrounded input line segment into a partition data structure indicating a first partition of the plane, the input unrounded line segment being represented by a set of real coordinates in the planes   accessing the partition data structure; the partition data structure including data indicating a prior set of unrounded line segments including a boundary set of unrounded line segments forming a rectangular boundary lying on the plane; locations in the partition data structure being capable of being specified with reference to a finite precision grid of tiles superimposed on the plane; each tile having a position included therein referred to as an integral point having finite precision coordinates; the set of real coordinates of the input unrounded line segment specifying a position within the rectangular boundary;   determining a plurality of tiles in the finite precision grid related to the input unrounded line segment using the prior set of unrounded line segments; the plurality of tiles in the finite precision grid related to the input unrounded line segment being hereafter referred to as a plurality of related hot pixels; each related hot pixel including an endpoint of the input unrounded line segment or at least one point on an unrounded line segment included in the partition data structure;   performing, for each related hot pixel, a rounding operation using the input unrounded line segment; the rounding operation replacing real coordinates of a nonintegral point on an unrounded line segment located within the boundary of the related hot pixel with the finite precision coordinates of the integral point of the related hot pixel; the rounding operation causing an unrounded line segment to be split into two fragment line segments, each referred to individually as a fragment and collectively as a polysegment, having a vertex at the integral point in the related hot pixel; each fragment produced by the rounding operation being referred to as belonging to the unrounded line segment from which it was produced;   adding the fragments of the polysegment to the partition data structure to produce a modified partition data structure;   storing the input unrounded line segment in the modified partition data structure; the input unrounded line segment being associated in the modified partition data structure with all of the fragments belonging to the unrounded line segment from which it was produced; and   displaying an arrangement of line segments using said modified partition data structure.     
     
     
       14. The article of manufacture of claim 13 wherein all regions in the plane indicated by the partition data structure include subregions referred to as cells; each cell having a standardized geometric shape having a fixed number of bounded sides; and wherein, when a region in the plane having a shape different from the standardized geometric shape is produced as a result of the processor adding the at least one fragment representing the unrounded line segment to the modified partition data structure, said instruction data further including instructions for adding line segments referred to as attachments to the modified partition data structure to produce at least one cell having a standardized geometric shape. 
     
     
       15. The article of manufacture of claim 13 wherein replacing the real coordinates of a nonintegral point on an unrounded line segment with the finite precision coordinates of the integral point of the related hot pixel is referred to as perturbing the unrounded line segment to the integral point of a related hot pixel; and said instruction data further including instructions for perturbing an endpoint of the input unrounded line segment located within the boundary of a related hot pixel to the integral point of the related hot pixel; and   perturbing an intersection point of the input unrounded line segment with an unrounded line segment included in the prior set of unrounded line segments located within the boundary of a related hot pixel to the integral point of the related hot pixel.