Boost logo

Boost :

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:

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, gregod at, cpdaniel at, john at