Trapezoidal Decomposition

Trapezoidal decomposition of polygons involves breaking a polygon into a series of smaller trapezoids.

I’ve been working on a project – gds2ecp – to decompose lithography design files into compound shapes that can be written by electron beam lithography.

I was sure that there would be an existing library to do the polygon decomposition for me, or at least get me part of the way, but I couldn’t find exactly what I was after.

Poly2tri.py

After much searching I found the library I was looking for: poly2tri.py. As far as I can work out this is an archived work as part of the C-based poly2tri project, which is for the triangulation of polygons.

The heavy lifting in poly2tri is done by seidel.py, which uses an algorithm based on “A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons“, a paper by Raimund Seidel

The algorithm finds the intersections of vertical lines eminating from the vertices building up the original polygon.

poly2trap.py

Since poly2tri.py actually goes beyond what I need I’ve put together a small script – poly2trap.py – to take the trapezoid output from seidel.py.

All of the hard work is done by seidel.py. The output I’m after is the trapezoids which define the initial shape.

Here’s an example of the output which uses the ‘dude’ example file.

More Testing Needed

poly2trap.py is currently almost completely untested – the base code seidel.py seems pretty solid, but since it came from the poly2tri ‘archive’, I’m not sure if it incorporates all of the features and bug-testing that may have been introduced later.

More testing required…