tim@tslvax.UUCP (Timothy Beres) (08/04/86)
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.asw@tony.UUCP (Tony Williams) (09/05/86)
In article <116@tslvax.UUCP> tim@tslvax.UUCP writes: > ><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. > The best reference I have seen is %A Martin E Newell %A Carlo H Sequin %T The Inside Story on Self-Intersecting Polygons %J Lambda %V 1 %N 2 %D Second Quarter, 1980 %P 20-24 Their algorithm allows the use of even-odd rule *or* non-zero winding number rule to determine the "inside" portions, and the same algorithm works. Decomposition into trapezoids comes for free. John Warnock described a graphics package which uses this algorithm. %T A Device Independent Graphics Imaging Model for use with Raster Devices %A J. Warnock %A D. K. Wyatt %J Computer Graphics %V 16 %N 3 %D 1982 I believe that the same algorithm is used inside PostScript interpreters. My PostScript manual says "A detailed, technical description of a similar imaging model has appeared in ..." the above reference. --------------------------------------------------------------------------- Tony Williams |Informatics Division UK JANET: asw@uk.ac.rl.vd |Rutherford Appleton Lab Usenet: {... | mcvax}!ukc!rlvd!asw |Chilton, Didcot ARPAnet: asw%vd.rl.ac.uk@ucl-cs.arpa |Oxon OX11 0QX, UK