Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!apple!vsi1!versatc!ritter
From: ritter@versatc.UUCP (Jack Ritter)
Newsgroups: comp.graphics
Subject: Re: Looking for Polygon Dissection Algorithm
Summary: Actual Implementation of Newall & Sequin
Message-ID: <15577@versatc.UUCP>
Date: 25 Feb 89 01:09:07 GMT
References: <7422@batcomputer.tn.cornell.edu> <726@microsoft.UUCP>
Organization: Versatec, Santa Clara, Ca. 95051
Lines: 28

> 
> I am posting this rather than mailing, as I have not seen this reference
> posted here before, and it really is the seminal paper on the subject.
> 
> "The Inside Story on Self-intersecting Polygons", Martin E Newell and
> Carlo H sequin, Lambda, Second Quarter 1980.
> 
> This does exactly what you want.

I recently implemented this algorithim. It breaks up an 
arbitrary self-intersecting polygon into a minimum number
of trapezoids. I did all calculations in fixed point (eg,
intercept calc and intersection calc.). It is FAST!!!
I used quick sort for both active edge list sort and
initial y sort. You must be careful of intersections and
intercepts rounding down to an end point.

For anyone interested in doing this algo: first get it to
work on a 5 point star, draw within a SMALL area, such
as 5 units by 5 units. This will create most of the
rounding down/up problems. Once this works, you have
yourself a robust mother.

-- 
	      ->  Even aliens think The Three Stooges are funny.  <-
   Jack Ritter, S/W Eng. Versatec, 2710 Walsh Av, Santa Clara, CA 95051
   Mail Stop 1-7.  (408)982-4332, or (408)988-2800 X 5743
   UUCP: {pyramid,mips,vsi1,arisia}!versatc!ritter