Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site tslvax.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!whuxcc!lcuxlm!akgua!akguc!codas!peora!ucf-cs!tslvax!tim
From: tim@tslvax.UUCP (Timothy Beres)
Newsgroups: net.graphics
Subject: Polygon breaking revisited
Message-ID: <116@tslvax.UUCP>
Date: Mon, 4-Aug-86 15:33:46 EDT
Article-I.D.: tslvax.116
Posted: Mon Aug  4 15:33:46 1986
Date-Received: Thu, 7-Aug-86 01:59:32 EDT
Distribution: net
Organization: Tech-Source Labs, Altamonte Springs, Florida
Lines: 26

Hi,

<thanks>
	A while back I asked for some help on decomposing a polygon
into trapezoids.  The response was excellent!  Thank you everyone.
I ended up implementing "An algorithm for shading of regions on 
vector display devices" by Brassel and Fegeas, ACM 1979.  They
deal with trapezoidation of polygons in the first part of the paper.
It was pretty easy to figure out what had to be done, though *lots*
of examples and extrapolation were necessary to figure out some of the
little "exercise left to the reader*" items in the algorithm.  I ended up
drawing lots of polygon chunks to identify these.

<followup request>
	The above algorithm works fine for non-intersecting polygons;
now, does anyone know of an algorithm to seperate a polygon into non-
intersecting parts?  The above algorithm will take it from there.

* Thank God for Calculus I: (Y - Y1) = M * (X - X1).  Just be sure to 
  check for an infinite slope!

			Tim

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