Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!agate!eos!jbm
From: jbm@eos.UUCP (Jeffrey Mulligan)
Newsgroups: comp.graphics
Subject: Re: Concave polygon problem
Message-ID: <3964@eos.UUCP>
Date: 13 Jun 89 19:06:40 GMT
References: <3378@cps3xx.UUCP>
Organization: NASA Ames Research Center, California
Lines: 50

From article <3378@cps3xx.UUCP>, by dulimart@cpsvax.cps.msu.edu (Hansye S. Dulimarta):

> 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

If the interior angle at p1 is greater than 180 degrees, then the
triangle into which you have "decomposed" the polygon actually lies
outside of the original polygon.  Testing this angle is not sufficient,
either:

               P2
               .
             ./
           . /
         .  /
       .   /
  P1 .    .  P3
       .   \
         .  \
           . \
	     .\
	       .

               P4

Here the angle at P1 is < 180, but triangle P1 P2 P4 contains area
outside the polygon.

> Do you get the idea ?

More half-baked speculation follows; hit 'n' now if you're
waiting for the literature citation.

A little doodling has convinced me that it is difficult to devise
an algorithm that will do this without testing that the cutting
segment lies entirely within the polygon.  An effective way to
reduce the search space, however, would seem to be to restrict
possible cutting segments to those having endpoint(s) which do
not lie on the convex hull.

-- 

	Jeff Mulligan (jbm@aurora.arc.nasa.gov)
	NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035
	(415) 694-6290