Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-09 12:33:14

Andriy Sydorchuk wrote:
>> 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.

So I am learning along with the students.  I'd like to thank Thomas for pointing out that my terminology has been imprecise.  In answer to Andriy's question, it is actually straight skeleton that I intended to suggest for the GSOC project.  I think it may be easier to focus on straight skeleton because if the output does not contain arcs then we don't need to provide interfaces and data structures for non-piecewise-linear geometry.  That is a bigger issue than it may seem at first because of numerical issues inherent in the way arcs are chosen to be represented.  On the other hand, if the student has a preference for implementing medial axis I would support that.

Sorry for the confusion,
Luke