Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-04-09 15:50:12

>
> 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

Well this is general approach used to solve problem with sweepline
algorithm. What I am asking about are algorithm details.
For voronoi diagram there is exact prototype of algorithm (as example "An
Efficient Implementation of Fortune’s Plane-Sweep Algorithm for Voronoi
Diagrams" KennyWong, Hausi A. Muller, page 18). This prototype is definitely
not the same for medial axis and straight skeleton problems. If it is common
approach to solve this problems with sweepline, so there should be some
articles and theory about that, but I haven't found them. Maybe I am
expected to develop this prototype on my own, am I?

(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.

Well lets consider that I know "current virtual construction", but it is not
so clear how to update it with moving further. For example how we should
deal with edges that are not visible yet but have influence on the "current
virtual construction". In the sweepline implementation for voronoi diagram
our "current virtual construction" lies above the sweepline datastructure
(union of arcs) and it is mathematically proven that it won't change with
further algorithm execution.

 It get's difficult when you start fighting with floating point arithmetic
> or integer coordinates rounding logic.

Yes, I understand that. But at first I'd like to be clear with all the
algorithm details.

Best regards,
Andrii