Converting complex polygons into simple polygons

Most algorithms in computational geometry for 2D polygons (e.g. polygon partition, Boolean operations, and offset curves) assume the input to be simple, that is, without self-intersections. Your task will be to develop and to implement an algorithm that takes as input an arbitrary complex polygon, with possible self-intersections and degeneracies, and generates as output a set of simple polygons that together enclose the same interior than the complex polygon. The ideal candidate for this project has good programming and mathematical skills and enjoys geometric thinking and reasoning.

Contact: