Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!usna!dfr From: dfr@usna.NAVY.MIL (Prof. David F. Rogers) Newsgroups: comp.graphics Subject: Re: concave polygon to convex polygons Message-ID: <397@usna.NAVY.MIL> Date: 12 May 91 00:19:37 GMT References: <383@usna.NAVY.MIL> Organization: U. S. Naval Academy, Annapolis, MD Lines: 30 In article lambert@silver.cs.umanitoba.ca (Tim Lambert) writes: !!!!!! 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.) The algorithm in Procedural Elements can be implimented such that the Steiner points are eliminated. When a concave polygon is found one takes the line from the vertex on the axis to the first vertex above the axis to split off the polygonal piece. Note it is possible that this split off piece may be concave so it must also be investigated. Dave Rogers