Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!aramis.rutgers.edu!athos.rutgers.edu!webber From: webber@athos.rutgers.edu (Bob Webber) Newsgroups: comp.graphics Subject: Re: Combining two Polygons - Algorithm?? Message-ID: Date: 25 Feb 90 12:00:39 GMT References: <20549@netnews.upenn.edu> <4279@helios.TAMU.EDU> <4916@becker.UUCP> Distribution: usa Organization: Rutgers Univ., New Brunswick, N.J. Lines: 33 In article <4916@becker.UUCP>, bdb@becker.UUCP (Bruce Becker) writes: > In article <4279@helios.TAMU.EDU> gordon@photon.tamu.edu (Dan Gordon) writes: > |In article <20549@netnews.upenn.edu> gururaj@eniac.seas.upenn.edu (Ravi Gururaj) writes: > |>Request: Algorithm to combine two polygons. > | > |Note that a very simple modification of the Weiler-Atherton clipping algorithm > |yields an algorithm that combines the 2 input polygons. It can handle concave > |polygons and holes as well. > > Some details (or pointers to same) > might well prove to be fascinating. I assume the relevant pointer would be: Keven Weiler, Polygon comparison using a graph representation, SIGGRAPH'80, 10-18. This came three years after Weiler & Atherton, Hidden surface removal using polygon clipping, SIGGRAPH'77, 214-222. The 1980 paper begins: All of the information necessary to perform that polygon set operations (union, intersection, and difference) and therefore polygon clipping can be generated by a single application of a process called polygon comparison. ... The algorithm is sufficiently general to compare sets of concave polygons with holes. More than two polygons can be compared at one time; all information for future comparisons of subsets of the original input polygon set is avaiilable from the results of the initial application of the process. The author viewed this as an improvement over the SIGGRAPH'77 approach due to greater simplicity, fewer special cases, etc. When the Weiler-Atherton algorithm was presented in Roger's Procedural Algorithms for Commputer Graphics, the '80 paper is cited as implementation details on the '77 paper. --- BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)