Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!sun-barr!cs.utexas.edu!csd4.milw.wisc.edu!uxc!tank!eecae!cps3xx!cpsvax!dulimart
From: dulimart@cpsvax.cps.msu.edu (Hansye S. Dulimarta)
Newsgroups: comp.graphics
Subject: Re: Concave polygon problem
Keywords: polygon fill concave convex
Message-ID: <3378@cps3xx.UUCP>
Date: 12 Jun 89 22:52:07 GMT
References: <32132@wlbr.IMSD.CONTEL.COM>
Sender: usenet@cps3xx.UUCP
Reply-To: dulimart@cpsvax.UUCP (Hansye S. Dulimarta)
Organization: Michigan State University, Computer Science Department
Lines: 37

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 have been unable to find such a  beast, but I know that it must  exist
>somewhere.
>
>Any ideas or references would be much appreciated.
>------
>Jim Macropol
>Contel Federal Systems		(818)706-5202
>jm@wlv.imsd.contel.com		wlbr!jm

Since triangle is a CONVEX polygon, we can decompose the general polygon
to a number of triangles. I don't have such algorithms / program to do that
but I just want to give you an idea of decomposing the polygon:

Let say that we have N-side polygon (which also implies N points in the
polygon). To simplify the notation let us label all points with
p1,p2,...,pN (start from a point in the polygon and go to the next adjacent
point in ONE direction : clockwise / counterclockwise)

procedure Decompose (N);
  comment - "decompose a N-side polygon into triangles"
begin
  (1) Pick the first point to start the decomposition (p1)
  (2) Contruct a triangle from point (p1, p2 and pN-1).
      After "removing" this triangle from the polygon we are left with
      a polygon with (N-2) sides
  (3) if the remaining polygon is still concave we still have to apply
      further decomposition. [We can do this by calling recursively to
      Decompose (N-2);]
end;

Do you get the idea ?