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