🚀 go-pugleaf

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