Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!samsung!uunet!bonnie.concordia.ca!ccu.umanitoba.ca!ccu.umanitoba.ca!lambert From: lambert@silver.cs.umanitoba.ca (Tim Lambert) Newsgroups: comp.graphics Subject: Re: concave polygon to convex polygons Message-ID: Date: 9 May 91 16:54:04 GMT References: <1991May6.071432.26483@netcom.COM> <383@usna.NAVY.MIL> Sender: news@ccu.umanitoba.ca Organization: Department of Computer Science, University of Manitoba Lines: 23 In-Reply-To: dfr@usna.NAVY.MIL's message of 8 May 91 13:38:07 GMT >>>>> On 8 May 91 13:38:07 GMT, dfr@usna.NAVY.MIL (Prof. David F. Rogers) said: > !!!!!! On 6 May 91 07:14:32 GMT, chet@netcom.netcom.COM (Eric Chet) said: > !! I have a polygon [that I want to split] into a minimum > !! number of convex polygons. > ... Procedural Elements for Computer Graphics by Rogers (see freq. > asked questions) [contains a] technique for spliting the concave > polygon into convex parts. It does not yield an optimal split in the > sense of the minimum number of convex polygons ... One more point: the technique described in Rogers introduces some new vertices at points where the extension of edges into the interior of the polygon intersects another edge. (These are known as Steiner points.) Depending on your application, this might not be desirable. (For example, if the vertices are expressed in integer coordinates, the Steiner points probably will not be.) A simple technique for a (non-minimal) split is to add diagonals between concave vertices. (You have to reject diagonals that intersect polygon edges.) Tim