Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utcs!mnetor!seismo!lll-crg!lll-lcc!vecpyr!amd!pesnta!peora!ucf-cs!tslvax!tim
From: tim@tslvax.UUCP
Newsgroups: net.graphics
Subject: Decomposing a polygon into a buncha trapezoids
Message-ID: <115@tslvax.UUCP>
Date: Fri, 11-Jul-86 17:17:13 EDT
Article-I.D.: tslvax.115
Posted: Fri Jul 11 17:17:13 1986
Date-Received: Sat, 12-Jul-86 22:34:17 EDT
Distribution: net
Organization: Tech-Source Labs, Altamonte Springs, Florida
Lines: 57

Hello, a long discussion about polygons follows...

	I am in the process of developing a routine to reduce a polygon
into a set of trapezoids.  What I want to do is this:

	Given a closed polygon with N points, I would like to be able to
	decompose it into a set of trapezoids that fully describe the
	polygon.  Each trapezoid have top and bottom segments (or point
	in the case of coincedence) that are parallel to each other and
	to the X-axis.  The vertical segments can be non-parallel.
	
	Example shapes could look like this,

	x-------x         x             x---x
	 \       \       | |             | |
           x-------x    x---x             x

        "normal" trap.  triangle     inverted triangle  square(not shown)

	A seemingly simple solution is to take the N points of the polygon
	and sort them according to Y minima.  This would produce a set of
	points S1..Sn.  To get the first trapezoid, the following simplified
	algorithm (mine) is:

	1.  From point S1, check to see if S2 has the same Y value; if it
	    does the bottom segment is the segment S1..S2; if it doesn't
	    the bottom segment is the point S1.

	2.  The top segment starts with S2, if S2 did not have the same Y
	    value as S1, else S3 (or S4 if S3 the same Y as S1, S2, S3...).
	    [The special case of a polygon being collinear is handled here]

	The following trapezoids may be found similarly by incrementing
	S?.  Where this all falls apart is the case of non-concave polygons.
	An example would be (excuse the art!):

	      {points numbered as the input list and the sorted list}

          P2,S5 x------------x P3,S6
		|            |
                |   x P6,S4  |
                |  /|        |
                | / x--------x P4,S3
                |/ P5,S2
          P1,S1 x

	The first trapezoid should be P1/P6.  The above alg. would try to
	give P1/P5 - no good.

My question is: how do I determine (efficiently) the correct trapezoid, given
the above example.  I would GREATLY appreciate any literature ref's or 
help.  Tear this apart if necessary!  I've searched a good bit, but found
little on this particular problem.  Thanks very much.

-- 
...!ihnp4!{duke, akgua}!ucf-cs!tslvax!tim 		Tim Beres
Tech-Source # subsidiary of Ciprico, Inc.