Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2010-04-09 21:24:19

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.

Regards,
Thomas