Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-08 18:00:07

Andriy Sydorchuk wrote:
>> I see now that your element is actually a bisector of two sites, the
>> moving point at which two parabolas intersect that traces line
>> segments of the veronoi diagram as the sweepline advances.
> 
> 
> Yes, you are right. Thanks for all the tips. I've already written my
> proposal.
> 
> If you implement Medial Axis with sweepline that works on non-convex
>> polygons with holes you have implmented an algorithm that can also
>> handle multiple non-overlapping polygons.
> 
> 
> Ok, I see. At the moment I am looking for docs about Medial Axis
> sweepline algo implementation. Maybe you have some references?

I'm surprised that you have written your proposal without detailed discussion of medial axis.

Here is a reference I was able to quickly find:
http://www.springerlink.com/content/796w76637460t384/

Medial Axis, also known as straight skeleton, is similar to the veronoi diagram which considers line segments as sites.  It is solved by a sweepline over bisectors and the algorithm is similar to Fortune's algorithm. 

Regards,
Luke