Find tunnel 'center line'?

views:

127

answers:

+3 Q:

Find tunnel 'center line'?

Hi All,

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?

+1 A:

Your diagram needs more freehand circles!

Joking aside, I assume the complaint about Delaunay triangulation is based on the runtime? How precise does your solution need to be? Can you improve runtime to an acceptable level by simply dropping proximate vertices?

They're likely to have a better answer for this question over at the GIS stackexchange site. Unfortunately, since it's beta, I can't vote to move the question over there, but I strongly encourage you to re-ask it there.

http://gis.stackexchange.com/

Paul McMillan 2010-10-21 01:34:17

Thanks Paul. I'll try there. I have some very large maps, and very limited runtime resources. My current requirements don't call for extreme accuracy. I want to be able to modify my map and not recalculate the whole triangulation, and the implementations I've seen of Delaunay allowing both removal and addition of points are either not very efficient or extremely complicated. I just have a feeling that there is a much easier way.

sje397 2010-10-21 01:40:08

I don't know how extensive your modifications are, but is recalculating just a subset of the data an option? There are good spatial partitioning schemes that would let you select only nearby stuff to work with.

Paul McMillan 2010-10-21 02:25:23

I have the data in an octree, and I expect that changes to the triangulation would be localized (as I understand the 'triangle flipping' concept) - but there is an element of 'floodfill' to the process as well since the tunnels are not always closed. I expect some scary edge-cases there when e.g. trying to move points near an an 'open end'.

sje397 2010-10-21 02:37:24

+2 A:

This is a pretty classic skeletonization problem; there are lots of algorithms available. Some algorithms work in principle on outline contours, but since almost everyone uses them on images, I'm not sure how available such things will be. Anyway, if you can just plot and fill the sewer outlines and then use a skeletonization algorithm, you could get something close to the midline (within pixel resolution).

Then you could walk along those lines and do a binary search with circles until you hit at least two separate line segments (three if you're at a branch point). The midpoint of the two spots you first hit, or the center of a circle touching the three points you first hit, is a good estimate of the center.

Rex Kerr 2010-10-21 05:42:41

A skeleton on it's own will be accurate enough. The problem is that the implementations I've found haven't dealt well with frequently changing map data (i.e. localized changes in very large maps).

sje397 2010-10-21 13:32:39

Most algorithms won't propagate local changes very far anyway--why not just cut out the local part of the map, re-skeletonize, and heal up any differences at the end (e.g. linear interpolation between the two answers over some distance)?

Rex Kerr 2010-10-21 14:22:10

+6 A:

belisarius 2010-10-25 09:38:08

Awesome answer. Apologies for not answering re flood-filling - the truth is I'm not really sure if that's a possibility. I will give it some thought. There's heaps here to think about. Thank you very much for putting in so much effort.

sje397 2010-10-25 09:56:30

@sje397 It was a lot of work, indeed. But also very fun!

belisarius 2010-10-25 10:05:41

+1. Impressive! And I have to imagine that a local re-fill wouldn't be too difficult after an initial annotation of tunnel widths per vertex (computed after the first fill). It shouldn't be too hard to cut out a region around the changes and apply something like this just to the cutout.

Rex Kerr 2010-10-25 19:47:24

@Rex Kerr The algorithms for deleting edges and merging graphs are not difficult. In fact I am already merging one point at a time. If the modified region has a simple geometric expression (rectangle, circle ...) the whole thing is easy. I think I'll post an example if the floodfill is viable.

belisarius 2010-10-26 00:31:23

@Rex Kerr To be more specific: Re-merging a modified area needs two geometric objects ..1) The modified area and 2) It's frontier in the original map. From the frontier you get the graph vertices to create candidate proximity edges with the new zone

belisarius 2010-10-26 01:01:47

@belisarius - Agreed. I don't think it will be a trivial change, but I don't see any huge conceptual problems with it if one can make certain assumptions about vertex spacing and such. Anyway, again, impressive!

Rex Kerr 2010-10-26 15:35:14

ansaurus

tags:

views:

answers:

Find tunnel 'center line'?

related questions