Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2010-04-09 08:09:34

Simonson, Lucanus J wrote:
> Andriy Sydorchuk wrote:
> > 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:
> http://www.springerlink.com/content/796w76637460t384/

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

[AA95]  	O. Aichholzer and F. Aurenhammer. Straight skeletons for general polygonal figures. Technical Report 432, Inst. for Theor. Comput. Sci., Graz Univ. of Technology, Graz, Austria, 1995.
[AAAG95]  	O. Aichholzer, D. Alberts, F. Aurenhammer, and B. Gärtner. A novel type of skeleton for polygons. J. Universal Comput. Sci., 1(12):752-761, 1995.
[LD03]  	R. G. Laycock and A. M. Day. Automatically generating roof models from building footprints. In The 11-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2003. Journal of WSCG - FULL Papers, volume 11, 2003.

The given link is actually the reference [AA95].

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

Regards,
Thomas