Path: utzoo!utgpu!news-server.csri.toronto.edu!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: 7 May 91 23:08:25 GMT References: <1991May6.071432.26483@netcom.COM> Sender: news@ccu.umanitoba.ca Organization: Department of Computer Science, University of Manitoba Lines: 11 In-Reply-To: chet@netcom.netcom.COM's message of 6 May 91 07:14:32 GMT >>>>> On 6 May 91 07:14:32 GMT, chet@netcom.netcom.COM (Eric Chet) said: > I have a polygon with N vertices. I first need to test if it's concave > or convex. If concave split it into a minimum number of convex polygons. You can test if a corner is convex by calculating the signed area of the triangle formed by the three vertices that define the corner. Splitting a polygon into a minimum number of convex polygons is quite tricky: See J. M. Kiel "Decomposing a Polygon into simpler components" SIAM J on Computing 14 799--817 (1985)