Path: utzoo!attcan!uunet!ginosko!aplcen!uakari.primate.wisc.edu!ames!henry.jpl.nasa.gov!elroy.jpl.nasa.gov!cit-vax!woolstar
From: woolstar@cit-vax.Caltech.Edu (John D Woolverton)
Newsgroups: comp.graphics
Subject: Re: Polygon Triangulation. (?)
Message-ID: <11921@cit-vax.Caltech.Edu>
Date: 16 Sep 89 01:06:46 GMT
References: <7918@cbmvax.UUCP>
Distribution: comp
Organization: California Institute of Technology
Lines: 30

>>Given a sequence of vertices that represent the points on a polygon. I need to
>>(somehow) reduce this into two (or more) smaller polygons that have a (new)
>>common edge. For example given the square (0,0) (1,0) (1,1) (0,1) I'd like to
>>produce the two polygons (triangles) (0,0) (0,1) (1,1) and (0,0) (1,1) (0,1).
>>The problem is that I have no way of knowing before I am given the list of
>>vertices whether the polygon is concave or convex (or how many vertices I'm
>>going to get). So I can't just arbitrarily choose a pair of vertices and create
>>a new edge. I can't even be sure that the polygon isn't self intersecting (i.e.
>>a figure-eight-type shape). This doesn't seem like a very easy problem (I've
>>scratched my head over this for a while), and my graphics text books don't
>>cover this sort of problem at all. Can anyone suggest where I should look for
>>ideas on how to reduce complex polygons to simpler ones? Thanks.

While looking at a polygon and trying to figure out where to start,
we hit apon some neet tricks.  To find a good corner to start with,
go through all the points, and find the most extreme point in either
axis (greatest x or y), and this angle will convex.  By taking
the cross product of the two sides this point is part of, and comparing
it to the other cross products, you can tell which angles are
convex, and which are concave.  This makes cutting up the polygon
easier.  (But still not trivial)

I speak from experience on this, as I am right in the middle,
of writing a program to break up concave polygons into 
smaller convex polygons.  A friend supposedly wrote a utility
to break up polygons into triangles only, but that is too far
for me.  (So the debugging goes on...)

	John d Woolverton, video bits
	  woolstar@csvax.caltech.edu