Polygon breaking revisited

Thread View: net.graphics

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Timothy Beres Mon, 04 Aug 1986 19:33

#1358

Author: Timothy Beres
Date: Mon, 04 Aug 1986 19:33

26 lines
1642 bytes

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.

Re: Polygon breaking revisited

#1422

Author: Tony Williams
Date: Fri, 05 Sep 1986 17:35

43 lines
1943 bytes

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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads