Trapezoidal Decomposition of Polygons in Python

By | February 5, 2015

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.

After much searching I found the library I was looking for: 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, 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.

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

All of the hard work is done by 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.

Trapezoidal DecompositionMore Testing Needed is currently almost completely untested – the base code 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…

python polygons

One thought on “Trapezoidal Decomposition of Polygons in Python

  1. Matthew Coombes

    Thats a very nice bit of code. and have been able to use it in matlab sucessfully. Thanks alot. Do you have any idea how to extract the adjacency info of all the trapazoids?

Comments are closed.