19

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?

I'm working in fairly raw C++.

Improve this question
3
  • gis.stackexchange.com/q/177/162 also deals with what you are looking for: skeletisation algorithms.
    – julien
    Oct 21, 2010 at 8:29
  • 3
    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, 2010 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, 2011 at 13:28

2 Answers 2

Reset to default
6

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

Improve this answer
2
  • I have some working code, using Delaunay. I'm really asking if there are other ways.
    – sje397
    Oct 21, 2010 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, 2010 at 14:45
4

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

Improve this answer
6
  • 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, 2010 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, 2010 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, 2010 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, 2010 at 16:22
  • The license for CGAL looks restrictive (i.e. v. expensive - this is commercial software).
    – sje397
    Oct 21, 2010 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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