ULC@PSUVM.BITNET (10/25/88)
Hi there .... would someone either point me in the direction of a reference or
suggest an algorithm to triangularize an arbitrarily concave/convex noninterse
cting flat polygon????
Much Thanks..
Jason Twamley...spencer@tut.cis.ohio-state.edu (Stephen Spencer) (10/26/88)
In article <58605ULC@PSUVM>, ULC@PSUVM.BITNET writes: > Hi there. Would someone either point me in the direction of a reference or > suggest an algorithm to triangularize an arbitrarily concave/convex > nonintersecting flat polygon???? If the polygon is convex, triangles (although not optimal) can be created by forming new polygons from vertices (1,2,3),(1,3,4),(1,4,5),...,(1,(n-1),n) where there are 'n' vertices in the original polygon. For a reference on how to (a) determine whether a polygon is concave or convex, and (b) how to split a concave polygon into convex polygons, try David Rogers' "Procedural Elements for Computer Graphics," pp. 146-152. -- Stephen Spencer, Supercomputer Graphics Research Specialist I Advanced Computing Center for the Arts and Design (ACCAD) The Ohio State University | (614) 292-3416 1224 Kinnear Road, Columbus OH 43212 | spencer@tut.cis.ohio-state.edu
pjs@granite.dec.com (Philip J. Schneider) (10/27/88)
In article <58605ULC@PSUVM> ULC@PSUVM.BITNET writes: >Hi there .... would someone either point me in the direction of a reference or >suggest an algorithm to triangularize an arbitrarily concave/convex noninterse >cting flat polygon???? > > Much Thanks.. > Jason Twamley... Here are a few: Schacter, B. "Decomposition of polygons into convex sets", IEEE Trans. on Computers, C-27, 11, November 1978, pp. 1078-1082. Feng, H., and Pavlidis, T. "Decomposition of polygons into simpler components", IEEE Trans. on Comp., C-14, June 1975, pp. 636-650. Lloyd, E., "On triangulations of a set of points in the plane", Master's thesis, MIT/LCS/TM-88, 1977. Rogers, David F., Procedural Elements for Computer Graphics, McGraw-Hill, 1985, pp. 146-152. Bykat, A. Automatic generation of triangular grid: I-Subdivision of a general polygon into convex subregions. II-Triangulation of convex polygons. Int. J. fo Numer. Methods Eng., 10, 1976, pp. 1329-1342. Garey, M. Johnson, D., Preparata, F., and Tarjan, R. Triangulating a simple polygon. Inf. Process. Lett., 7, 4, 1978, pp. 175-179. Lewis, B. A., and Robinson, J. S. Triangulation of planar regions with applications. Comput. J. 21, 4, 1979, pp. 324-332. Tor, S. B. and Middleditch, A. E. Convex decomposition of simple polygons. ACM Trans. on Graphics, 3, 4, October 1984, pp. 244-265. Harrington, S. Computer Graphics - A Programming Approach. McGraw-Hill, 1983, pp. 345-352. I hope this gives you a start . . . -- Philip J. Schneider | pjs@decwrl.dec.com DEC Workstation Systems Engineering | pjs@granite.dec.com 100 Hamilton Avenue | (415)853-6538 Palo Alto, CA 94301 | (415)327-4922