# Find tunnel 'center line'?

I have some map files consisting of 'polylines' (each line is just a list of vertices) representing tunnels, and I want to try and find the tunnel 'center line' (shown, roughly, in red below).

I've had some success in the past using Delaunay triangulation but I'd like to avoid that method as it does not (in general) allow for easy/frequent modification of my map data.

Any ideas on how I might be able to do this?

Thanks.

P.S. I'm working in fairly raw C++, and was referred here from Stack Overflow.

-
I think the cross link with SO is relevant since there are answers there too stackoverflow.com/questions/3983613/find-tunnel-center-line – Dr. belisarius Oct 25 '10 at 13:16

You have drawn a good approximation to the Medial Axis Transform. The Delaunay triangulation indeed offers a good approach to it. (The principal challenge is that parts of the MAT are pieces of parabolas, not just line segments.)

I have run across references to working code (usually in C/C++ I recall) in the academic literature. Do a search on Google Scholar and look for older papers (the newer ones seem to be focusing on 3D calculations).

-
I have some working code, using Delaunay. I'm really asking if there are other ways. – sje397 Oct 21 '10 at 13:20
@sje397 First of all, Delaunay only approximately solves the problem, so for that reason alone it can be worth researching better code. Second, there are indeed other ways. I can outline two briefly: (1) search for the MAT by means of internal buffers and (2) perform terrain analysis on the Euclidean distance grid of the polylines. I did not mention either because both are much more inefficient and yield poorer results. Conceivably the second method is amenable to a reasonably fast dynamic solution. – whuber Oct 21 '10 at 14:45
I'll look into those. Thanks @whuber. – sje397 Oct 21 '10 at 23:26

It might be worth looking into "polygon skeletons".

There is some C++ source sample at http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

-
Thanks underdark. I will look further into CGAL. But the requirement that the recalculation isn't expensive when my map data changes is the difficulty. – sje397 Oct 21 '10 at 13:19
CGAL is quite fast - an on the fly computation should be possible. Otherwise, you could have a look at the so-called 'kinetic data structures': cgal.org/Manual/3.3/doc_html/cgal_manual/… – julien Oct 21 '10 at 14:34
The "skeleton" is another term for the MAT. Searching for "medial axis transform" has yielded more and better hits than searches on "skeleton" in my experience. – whuber Oct 21 '10 at 14:47
"skeleton" seems more generic - MAT is only one specific algorithm for skeleton, right? Whatever, it is not the topic...! – julien Oct 21 '10 at 16:22
The license for CGAL looks restrictive (i.e. v. expensive - this is commercial software). – sje397 Oct 21 '10 at 23:20

This question also deal with what you are looking for: skeletisation algorithms.

Have a look !

-
Thanks julien. Please see my comment on underdark's answer. That other question has some really useful info. – sje397 Oct 21 '10 at 13:21
you're welcome. see my comment to your comment on underdark's answer ! – julien Oct 21 '10 at 14:37