The impementation of the algorithm can be found in trapezoid.c and
trapezoid.h. The only public function in trapezoid.c is trapezoidalDecomposition
which
takes in a polygon (in integer coordinates) and outputs a list of
trapezia.
It first builds the Edge Table (makeEdgeTable
), and then
processes the Edge Table (processET
), using the plane sweep approach.
Note that rather than provide one function for outputting the trapezia, there are four very similar functions, for the cases A, B, C&D&E, and F. (I prefer this rather than creating one larger function with lots of special cases!).
The functions rely on a library (index.c
) for creating and
manipulating linked lists. Here a linked list of general pointers is
used to represent edges and trapezia, and also a linked list of ints
forms the ordered list of vertex y-values.
There are two interfaces. One is interactive and implemented in
OpenGL,
making use of the GLUT library for the windows and interface
components. The main file for this is maingltrap.c
. The
other uses X11 Xlib functions only (mainxtrap.c). The second one
actually implements the simple fill trapezium function. The Makefile
deals with both interfaces, use
% make xtrap
% make gltrap
depending on which one is required.
The source files can be downloaded using ftp, or if local, copied from my public directory.
Mel Slater, November 1997.