Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk