Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Patent
1995-12-29
1998-05-05
Nguyen, Phu K.
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
G06T 300
Patent
active
057481970
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.
REFERENCES:
patent: 5506948 (1996-04-01), Onitake et al.
patent: 5574839 (1996-11-01), Gangnet et al.
Nahed, A. and Peroche, B., "A 2 1/2D hierarchical model based on planar maps", Computers and Graphics, vol. 20, No. 1, Jan./Feb., 1996, 99. 115-123.
Jon L. Bentley and T.A. Ottmann, "Algorithms for Reporting and Counting Geometric Intersections," IEEE Transactions on Computers, vol. C-28, No. 9, Sep. 1979, pp. 643-647.
K.L. Clarkson and P.W. Shor, "Applications of Random Sampling in Computational Geometry, II", Discrete and Computational Geometry, v.4, 1989, pp. 387-421.
B. Chazelle and H. Edelsbrunner, "An Optimal Algorithm for Intersecting Line Segments in the Plane",Journal of the Association for Computing Machinery, vol. 39, No. 1, Jan. 1992, pp. 1-54.
Ketan Mulmuley,Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, Englewood Cliffs, N.J., 1994.
Ketan Mulmuley, in "A fast planar partition algorithm I", Journal of Symbolic Computation, v. 10, pp. 253-280, 1990.
Ketan Mulmuley, "Randomized Multidimensional Search Trees: Dynamic Sampling," Proceedings of the 7th ACM Symposium on Computational Geometry (SCG,) 1991, pp. 121-131.
Daniel H. Greene and Frances F. Yao, "Finite-Resolution Computational Geometry," Proc. 27th Ann. Symp. on Foundations of Computer Science, 1986, pp. 143-152.
M. Gangnet, J-C Herve, T. Pudet and J-M Van Thong, "Incremental Computation of Planar Maps,"Computer Graphics (SIGGRAPH '89), vol. 23, No. 3, 1989, pp. 345-354.
H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel and M. Sharir, "Arrangements of Curves in the Plane-Topology, Combinatorics, and Algorithms", Theoretical Computer Science 92 (1992), pp. 319-336.
Guibas Leonidas John
Marimont David H.
Nguyen Phu K.
Vo Cliff N.
Xerox Corporation
LandOfFree
Dynamic computation of a line segment arrangement using finite p does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic computation of a line segment arrangement using finite p, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic computation of a line segment arrangement using finite p will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-59555