Trapezoidal Decomposition

An Implementation in C

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.