Re: [boost] GSoC2010 Sweepline Algorithm

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 (
> 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/asydorchuk/t127068181731)
+ 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