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
> 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:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk