Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!mcvax!ukc!warwick!rlvd!asw
From: asw@tony.UUCP (Tony Williams)
Newsgroups: net.graphics
Subject: Re: Polygon breaking revisited
Message-ID: <1630@rlvd.UUCP>
Date: Fri, 5-Sep-86 13:35:37 EDT
Article-I.D.: rlvd.1630
Posted: Fri Sep  5 13:35:37 1986
Date-Received: Sat, 6-Sep-86 05:47:35 EDT
References: <116@tslvax.UUCP>
Sender: news@rlvd.UUCP
Reply-To: asw@rlvd.UUCP (Tony Williams)
Distribution: net
Organization: Informatics Division, R.A.L
Lines: 43

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