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
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
+ 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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk