Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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

alt text

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.

share|improve this question
1  
I think the cross link with SO is relevant since there are answers there too stackoverflow.com/questions/3983613/find-tunnel-center-line –  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
add comment

3 Answers

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

share|improve this answer
    
I have some working code, using Delaunay. I'm really asking if there are other ways. –  sje397 Oct 21 '10 at 13:20
1  
@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
add comment

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

share|improve this answer
    
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
show 1 more comment

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

Have a look !

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.