Boost logo

Boost :

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-04-12 12:08:46

> In any case the Felkel algorithm for straight skeleton (
> )
> 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 (
+ 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

start of July - end of July: finish straight skeleton generic

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!

Boost list run by bdawes at, gregod at, cpdaniel at, john at