Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2010-04-09 14:59:48

Andriy Sydorchuk wrote:
> In any case during last few days I was trying to find how to solve both
> of this problems (medial axis and straight skeleton) with sweepline
> algorithm and haven't found anything (theory, articles). Are you sure that any of
> them can be solved with sweepline?

Of course. It's the same argument as for the voronoi diagram. You sweep the line over the polygon, and nothing right of the sweepline enters into the "current virtual construction". So for a specific sweepline position, the virtual polygon that you have is the one that is the original polygon clipped by the sweepline, and your "current virtual construction" is probably the straight line skeletton (or the medial axis) of this virtual polygon.

(When "virtually" moving the sweepline now, you know how the "current virtual construction" will change, if all the clipped sides just continue straight. But this is the easy (and fun) part of the problem, and the sweepline paradigm is probably clear anyway. It get's difficult when you start fighting with floating point arithmetic or integer coordinates rounding logic.

Regards,
Thomas