Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Patent
1995-10-23
1998-06-23
Fetting, Anton
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
G06T 1720
Patent
active
057710457
ABSTRACT:
A method for decomposing a polygon into trapezoids and further decomposing the trapezoids. During the decomposition process, the method classifies vertices having a horizontal edge by traversing the active trapezoid list, and using the trapezoids found in the list to aid in classifying the vertex. When a polygon fully contains another polygon, the method slits a diagonal between the outside polygon and the inside polygon to create a single polygon. During the slitting produces, vertices are duplicated and diagonals connecting to the original vertex are left connected to the original vertex or are connected to the duplicated vertex. The method corrects improper ordering of the inside polygon, and the method provides consistency checks during the decomposition process to detect polygons with intersecting edges.
REFERENCES:
patent: 5043711 (1991-08-01), Harrington
patent: 5129051 (1992-07-01), Cain
patent: 5133049 (1992-07-01), Cain et al.
patent: 5317681 (1994-05-01), Glassner
patent: 5428717 (1995-06-01), Glassner
patent: 5553206 (1996-09-01), Meshkat
patent: 5623790 (1997-04-01), Lalvani
Chiang et al., Time-Efficient VLSI Artwork Analysis Algorithms in GOALIE2, IEEE Transactions on Computer-Aided Design, v.8,n.6,pp. 640-648, Jun. 1989.
Nagesawara, Robot Navigation in Unknown Generalized Polygonal Terrains Using Vision Sensors, IEEE Transactions on Systems, Man, and Cybernetics, v.25,n.6,pp. 947-962, Jun. 1995.
Chi, A Method For Net Representation With Polygon Decomposition, IEEE, pp. 222-225, May 1988.
"Multi-dimensional Searching and Computational Geometry" by Kurt Mehlhorn; EATCS Monographs on Theoretical Computer Science; Springer-Verlag 1984; pp. 79-83.
"Triangulating Simple Polygons and Equivalent Problems" by Alain Fournier and Delfin Y. Montuno; ACM Transactions on Graphics, vol. 3, No. 2, Apr. 1984, pp. 153-174.
"A Fast Las Vegas Algorithm For Triangulating a Simple Polygon" by Kenneth L. Clarkson et al.; Proc. of the 4.sup.th Annual ACM Symp. on Computational Geometry, 1988; pp. 18-21.
"The Graham Scan Triangulates Simple Polygons" by Xianshu Kong et al.; Pattern Recognition Letters, 11 (1990); pp. 713-716.
"Fast Triangulation of Simple Polygons" by Stefan Hertel et al.; 4.sup.th Conf. Foundations of Computation Theory; Springer-Verlag LNCS 158 (1983); pp. 207-218.
"Triangulating a Polygon in Parallel" by Michael T. Goodrich; Journal of Algorithms, 10 (1989); pp. 327-351.
"Triangulation and Shape-Complexity" by Bernard Chazelle et al.; ACM Transactions on Graphics, vol. 3, No. 2, Apr. 1984; pp. 135-152.
"Triangulating a Simple Polygon in Linear Time" by Bernard Chazelle; Discrete Computer Geometry 6 (1991); pp. 485-524.
"Decomposing a Polygon Into Its Convex Parts" by Bernard Chazelle et al.; Proceedings of the 11.sup.th ACM Symposium on Theory of Computing; Atlanta, GA. 1979; pp. 38-48.
"A Linear-Time Algorithm for Triangulating Simple Polygons" by Robert E. Tarjan et al.; Proc. 18.sup.th Annual ACM Symposium on Theory of Computing, 1986; pp. 380-388.
"An O(n log log n)-Time Algorithm For Triangulating A Simple Polygon" by Robert E. Tarjan et al.; SIAM Journal of Comput. 17 (1988); pp. 143-178.
"Decomposition of Polygons Into Simpler Components: Feature Generation For Syntactic Pattern Recognition" by Hou-Yuan F. Feng et al.; IEEE Trans. on Computers, vol. C-24, No. 6, Jun. 1975; pp. 636-650.
"Decomposition of Polygons Into convex Sets" by Bruce Schachter; IEEE Trans. Computers C-72(11); Nov. 1978; pp. 1078-1082.
"The Decomposition of Polygons Into Convex Parts" by Daniel H. Greene; In Adv. Comput. Res., F.P. Preparata, ed., JAI Press Inc. (1983); pp. 235-259.
"On Partitioning Polygons" by Andrsej Lingas; In Proc. 1.sup.st Annual ACM Symposium Comput. Geom. (1985). pp. 288-295.
1.15. Preparate, F.P. An Optimal Real Time Algorithm for Planar Convex Hulls. Commun. ACM 22 (1979), pp. 402-405.
"A Linear Time Algorithm For Triangulating A Point-Visible Polygon" by T.C. Woo et al.; ACM Trans. on Graphics, 4 (1985); pp. 60-69.
"Convex Decomposition of Simple Polygons" by S.B. Tor et al.; ACM Trans. on Graphics, vol. 3, No. 4, Oct. 1984; pp. 244-265.
"An Optimal Algorithm For Finding The Kernel Of A Polygon" by D.T. Lee et al.; Journal of the Association for Computing Machinery, vol. 26, No. 3; Jul. 1979; pp. 415-421.
"Two Algorithms for Constructing A Delaunay Triangulation" by D.T. Lee et al.; International Journal of Computer and Information Sciences, vol. 9, No. 3, 1980; pp. 219-242.
"Some NP-Hard Polygon Decomposition Problems" by Joseph O'Rourke et al.; IEEE Transactions on Information Theory, vol. IT-29, No. 2; Mar. 1983; pp. 181-190.
"Polygon Decomposition And Switching Function Minimization" by J. O'Rourke; Computer Graphics And Image Processing 18; (1982); pp. 382-391.
"A Theorem On Polygon Cutting With Applications" by Bernard Chazelle; 23.sup.rd Annual Symposium on Foundations of Computer Science; 1982; pp. 339-349.
"Minimum Decompositions of Polygonal Objects" by J.M. Keil et al.; In Computational Geometry, G.T. Toussaint, ed., North-Holland (1985); pp. 197-212.
"On Finding the Convex Hull of a Simple Polygon" by D.T. Lee; International Journal of Computer and Information Sciences, vol. 12, No. 2; 1983; pp. 87-98.
"Decomposing a Polygon into Simpler Components" by J.M. Keil; SIAM Journal of Comput. 14 (1985); pp. 799-817.
"Triangulation of Planar Regions with Applications" by B.A. Lewis et al.; Computer Journal, vol. 21, No. 4; Nov. 1978; pp. 324-332.
"A Heuristic Triangulation Algorithm" by David A. Plaistad et al.; Journal of Algorithms 8 (1987); pp. 405-437.
"Partitioning a Polygonal Region into a Minimum Number of Triangles" by Tetsuo Asano et al.; Trans. IECE Japan E67 (1984), pp. 232-233.
"Closest-Point Problems" by M.I. Shamos et al.; Proc. IEEE Symp. on Foundations of Computer Science 16; (1975); pp. 151-162.
"The Art Gallery Theorem for Polygons with Holes" by F. Hoffman et al.; Proc. 32.sup.nd Annual Symposium on Foundations of Computer Science; Publisher: IEEE Computer Science Press, Oct. 1991; pp. 39-48.
"A Fast Convex Hull Algorithm" by Selim G. Akl et al.; Information Processing Letters, 7 (1970); pp. 219-222.
"Triangulating a Simple Polygon" by Michael R. Garey et al.; Information Processing Letters, 7 (1978); pp. 175-179.
"Another Efficient Algorithm for Convex Hulls in Two Dimensions" by A.M. Andrew; Information Processing Letters, 9 (1979); pp. 216-219.
"Convex Hull of a Finite Set of Points in Two Dimensions" by A. Bykat; Information Processing Letters, 7 (1978); pp. 296-298.
"Finding the Convex Hull of a Simple Polygon" by Ronald L. Graham et al.; Journal of Algorithms. To Be Published.
"A Linear Algorithm for Finding the Convex Hull of a Simple Polygon" by Duncan McCallum et al.; Information Processing Letters, 9 (1979); pp. 201-205.
"Traditional Galleries Require Fewer Watchmen" by J. Kahn et al.; SIAM Journal of Algebraic and Discrete Methods, vol. 4, No. 2; 1983; pp. 194-206.
"A Non-Hamiltonian, Nondegenerate Delaunay Triangulation" by M.B. Dillencourt; Information Processing Letters, 25 (1987); pp. 149-151.
"Traveling Salesman Cycles are Not Always Subgraphs of Delaunay Triangulations or of Minimum Weight Triangulations" by M.B. Dillencourt; Information Processing Letters, 24 (1987); pp. 339-342.
Cunniff Ross
Ghavam Karen M.
Fetting Anton
Hewlett--Packard Company
LandOfFree
Method for polygon decomposition does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for polygon decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for polygon decomposition will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1397896