trainor@CS.UCLA.EDU (06/23/87)
In article <859@pixar.UUCP> ph@pixar.UUCP (Paul Heckbert) writes: >POLYGON TYPE TIME METHOD > >star O(logn) binary search on angle from "center" of polygon, test > inclusion in a single triangle > (decompose polygon into triangles radiating from center) > this method requires preprocessing. I'm glad to finally see some discussion of complexity in this group! The question I have is why isn't preprocessing pervasive? If there are only a small number of tests per polygon, or the number of edges is small, sure, other than that, the use of clever data structures ``wins.'' How many people out there raytrace polygonal objects? Dobkin & Lipton are credited by Preparata & Shamos for the notion of creating new geometric objects to permit binary searching. I forgot the reference, but a lot more than just star-shaped polygons can be tested in O(log n) time. The basic idea is to build a tree data structure that partitions the polygon into regions, and later, regions that do not influence the decision are not tested against. I advocate the multiple implementation approach, enabling the algorithm that fits with your particular input distribution. It really counts if you are at all interested in making movies, and your artists go gonzo with polygons. Perhaps we need a speed-based point-polygon contest for the raytracers. I am interested in how many universities have graduate courses in computational geometry. A seminar doesn't get as many points, but I am still interested... Please send directly to <trainor@cs.ucla.edu> Douglas [][] trainor@cs.ucla.edu [][] ..!{sch-loki,silogic,randvax,ucbvax}!ucla-cs!trainor [][] trainor@eric.sidewinder.snake