Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!mit-eddie!uw-beaver!rice!titan!foo
From: foo@titan.rice.edu (Mark Hall)
Newsgroups: comp.graphics
Subject: Re: Concave polygon problem
Keywords: polygon fill concave convex
Message-ID: <3501@kalliope.rice.edu>
Date: 13 Jun 89 01:50:36 GMT
References: <32132@wlbr.IMSD.CONTEL.COM> <3378@cps3xx.UUCP>
Sender: usenet@rice.edu
Reply-To: foo@titan.rice.edu (Mark Hall)
Organization: Rice University, Houston
Lines: 55

In article <3378@cps3xx.UUCP> dulimart@cpsvax.UUCP (Hansye S. Dulimarta) writes:
>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. 

>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 ?

                   P4
                  *-------------------------------*
                 /                                 \
                /                                   \
               *  P3                                 \
                \                                     \
                 \                                     \
                  * P2                                  \
                  |                    *(inside)         *
                  |                                     /
                  * P1                                 /
                 /                                    /
                /                                    /
               * Pn-1                               /
                \                                  /
                 \  Pn-2                          /
                  *------------------------------*



    One problem with your algorithm: It fails for concave polygons. 
  (Which is what it is needed for.) The triangle defined by points
  P1, P2, Pn-1 does not have to be in the polygon at all. 

    Did I miss something?

 - mark