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: <383@usna.NAVY.MIL>
Date: 8 May 91 13:38:07 GMT
References: <1991May6.071432.26483@netcom.COM> <LAMBERT.91May7190825@silver.cs.umanitoba.ca>
Organization: U. S. Naval Academy, Annapolis, MD
Lines: 23

In article <LAMBERT.91May7190825@silver.cs.umanitoba.ca> lambert@silver.cs.umanitoba.ca (Tim Lambert) writes:
!!!!!! 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)

One technique of implimenting this technique is described in
Procedural Elements for Computer Graphics by Rogers (see freq. asked
questions). A fall out of this implementation is 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
but it will split the concave polygon into convex parts. Getting the
minimum number of convex parts is the really tricky part. But in
some applications this is not critical.

Dave Rogers