Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-04-09 10:46:43

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

It is my fault, but I've just returned from my internship in another
country. That's why I had not enough time to discuss that and student
application deadline is 9th of April (actually today). Probably we still can
discuss it before end of the Interim Period (April 21).

Some more references:

[CGAL]
> http://www.cgal.org/Manual/last/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

...

The given link is actually the reference [AA95].

Thanks for the links. I actually started to look at
http://www.cgal.org/Manual/last/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html
.

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

> There are actually subtle differences between "Medial Axis", "straight
> skeleton" and the "voronoi diagram" of a polygon. A more detailed
> explanation of the differences can be found in the reference [CGAL], for
> example. However, from the comment "Medial Axis, also known as straight
> skeleton", I conclude that the project Luke has in mind is to compute the
> "straight skeleton", which he prefers to call "Medial Axis". This mixing of
> names is not uncommon, so you better get used to it.

So do we need to compute straight skeleton (it consists only of straight
line segments) or medial axis (may also include parabolic arcs)?
Medial axis seems to be more similar to Voronoi diagrams (instead of sites
input it uses edges as Luke said). So I am quite not sure if we should
compute straight skeleton there.