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/Cha...
...
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_... .
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