# Finding 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?

I'm working in fairly raw C++.

• gis.stackexchange.com/q/177/162 also deals with what you are looking for: skeletisation algorithms. – julien Oct 21 '10 at 8:29
• 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
• @julien: You already linked that in your answer. I read through it, but it doesn't answer my specific question (which, to rephrase, is: 'I already know how to find the MAT - but I am wondering if anyone knows a non-Delaunay algorithm [i.e. not a lib - the problem is not my coding ;)] that is efficient for localized changes'). There was an answer on SO that didn't quite answer either but took a lot of effort and gave me plenty to think about so I've awarded the check to that guy until something better comes along. None of the answers below are that good (which may well be my fault). – sje397 Jan 20 '11 at 13:28

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

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