In any case the Felkel algorithm for straight skeleton ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.5505&rep=rep1&type=ps ) appears to be the one to implement according to Fernando, who ought to know. Felkel provides a step by step breakdown of the algorithm, which is more of a spiraling inward on closed polygons and shows how it can be applied to non-convex polygons with holes. This isn't a sweepline, it is a wavefront algorithm. If you imagine the roofline analogy the algorithm is rising water.
This is exactly what I was looking for. Thanks a lot. I've already explored part connected with convex polygons, everything seems to be clear. I for some reason had in my mind a veronoi diagram -> medial axis ->
straight skeleton progression of algorithm. It turns out that straight skeleton, despite being superficially similar to medial axis, is not solved the same way. So while I would like to see a straight skeleton implementation because it leads to a number of very nice polygon operations, straight skeleton may have to wait until next year or I may end up implementing it myself
At the moment my proposal only includes Voronoi and Delaunay triangulation problems, as I removed everything about medial axis or straight skeleton before things would become clear. As I am not able to edit my proposal after 9th of April I'll add changes there: During GSoC I am ready to implement everything that I mentioned in my proposal ( http://socghop.appspot.com/gsoc/student_proposal/private/google/gsoc2010/asy...) + straight skeleton generic implementation (with visualization tool). After GSoC I am ready to continue our collaboration and implement medial axis algorithm also. Proposed Milestones and Schedule will look like this: Proposed Milestones and Schedule Present - end of May: design basic architecture, write test cases, read articles connected with the topic, learn Boost; start of June - end of June: finish Voronoi and Delaunay triangulation implementation; start of July - end of July: finish straight skeleton generic implementation; start of August - 20th of August: improve logic, make refactoring, work on performance, testing, finishing documentation, benchmark tests. If you expect something else, please let me know. Thanks Luke, Thomas! Andrii