# 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. 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 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. 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. 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. 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/… 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. 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...! Oct 21 '10 at 16:22
• The license for CGAL looks restrictive (i.e. v. expensive - this is commercial software). Oct 21 '10 at 23:20