Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-12 02:14:53

Thomas Klimpel wrote:
> Andriy Sydorchuk wrote:
>>> For example how we should deal with edges that are not visible
>>> yet but have influence on the "current virtual construction".
>> 
>> I agree, this statement was wrong by the definition of "beach line"
>> and "sweep line". Basically I was trying to find analog of "beach
>> line" in case of "straight skeleton" and "Medial Axis". In case of
>> "Medial Axis" it will be something similar to Fortune's "beach
>> line". However it is not so clear what it is in case of "straight
>> skeleton" problem. I'll do further research in the given area.
> 
> You are probably right that there doesn't exist a "beach line" in
> case of the "straight skeleton" problem for an arbitrary non-convex
> polygon. For a reflective vertex with angle alpha, the actual
> distance of the spliting point can actually be up to  "1 / sin
> (alpha/2)" further away from the "sweep line" than the direct
> distance to the "sweep line". Since the angle alpha can be arbitrary
> small, the influence range of these reflective vertices cannot be
> bounded, hence there doesn't exist a real "beach line" as required
> for the straightforward application of the sweepline paradigm.        
> 
> So whatever the references Luke found described, it probably wasn't
> the straightforward application of the sweepline paradigm to the
> "straight skeleton" problem, as this would not be directly applicable
> to polygons without a lower bound for the minimum reflective vertex
> angle. However, convex polygons, manhattan polygons and 45 degree
> angle polygons all have such a lower bound, so a "straightforward"
> sweepline algorithm for the "straight skeleton" problem might still
> make sense to have for Boost.Polygon.       
> 
> Let's hope I finally managed to create some confusion.

There has been some confusion from the beginning.  What you have finally managed to create is doubt, which has lead me to recheck my assumptions.  This is what I get for not doing the research *before* suggesting the project idea.

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.

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.

Thanks Thomas,
Luke