Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!hplabs!nsc!voder!berlioz!nelson
From: nelson@berlioz (Ted Nelson)
Newsgroups: comp.graphics
Subject: Re: Concave polygon problem
Keywords: polygon fill concave convex
Message-ID: <326@berlioz.nsc.com>
Date: 7 Jun 89 23:35:06 GMT
References: <32132@wlbr.IMSD.CONTEL.COM>
Reply-To: nelson@berlioz.UUCP (Ted Nelson)
Organization: National Semiconductor, Santa Clara
Lines: 13

In article <32132@wlbr.IMSD.CONTEL.COM> jm@wlbr.imsd.contel.com (James Macropol) writes:
>I have been  looking for an  algorithm to convert  a (possibly)  concave
>polygon into a set  of convex polygons  that cover the  same area.   The
>algorithm need not be  optimal, but should do  a reasonable job, and  be
>fast.

I found a nice, simple one to degenerate into horizontal trapezoids.  You
can find it in ACM Trans Graphics Vol 3, No 2, April 1984, pp 153-174
called "Triangulating Simple Polygons and Equivalent Problems." by Fournier
and Montuno.  Don't be thrown by the title, the algorithm you want is 
presented completely in the first 5 pages.

-- Ted.