Path: utzoo!attcan!uunet!ogicse!uwm.edu!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!metro!usage.csd.unsw.oz.au!usage.csd!lambert
From: lambert@spectrum.eecs.unsw.oz (Tim Lambert)
Newsgroups: comp.graphics
Subject: Re: Triangulating concave polygons
Message-ID: <LAMBERT.90Jun1122908@nankeen.spectrum.cs.unsw.oz.au>
Date: 1 Jun 90 02:29:07 GMT
References: <807@fsu.scri.fsu.edu> <1990May29.212826.3457@everexn.uucp>
Sender: news@usage.csd.unsw.oz.au
Organization: none
Lines: 27
In-reply-to: roger@everexn.uucp's message of 29 May 90 21:28:26 GMT

>>>>> On 29 May 90 21:28:26 GMT, roger@everexn.uucp (Roger House) said:
 
% Let Pi be any vertex of the polygon.  Let Ph be the vertex preceding Pi,
% and let Pj be the vertex following Pi.  Test if angle PhPiPj is convex.
% If not, increment i, determine h and j from i, and test again.  If a 
% convex angle is not found by this process, there is an error in the 
% polygon.  It is either not well-formed, or it is oriented clockwise.
 
% Once a convex angle PhPiPj is found, the triangle formed by the three 
% points is a candidate.  However, it is ONLY a candidate.  It must be
% tested like this:  For every vertex V of the polygon other than the three
% forming the triangle, test if V is OUTSIDE the triangle (note that V 
% must not be ON the boundary of the triangle).  If some vertex is found
% which is either on the boundary of or inside of the triangle, then the
% triangle must be rejected.  In this case, increment i and continue 
% searching for a convex angle.
 
% If all V are outside of the triangle, then slice the triangle off the
% polygon by removing vertex Pi.  If the number of points in the resulting
% polygon is 3, then the decomposition is finished.  Otherwise, search
% again from a convex angle.

It is possible to construct triangles for which this algorithm takes
O(n^3) time.  If you get triangles like this with a lot of points,
this algorithm will probably be unacceptably slow.

Tim