9

I have a number of GPX tracks of the same road. But due to GPS error they are not accurate enough (20-30m off).

I'm wondering if I could interpolate those multiple gpx tracks into single one. If an error is random, interpolation should give me more accurate data.

Are there any algorithms to interpolate multiple (non-ordered) points?

Update I've found the correct search term. It's map inference gps traces in google scholar . There you can find "cited by" and related articles.

Improve this question
  • I see that you provide an answer to your question. Does it mean that it is solved ? Also, do you want to interpolate the height or to find the median line ? – radouxju Sep 11 '14 at 5:45
  • No, It's just random thoughts on an algorithm. That was before I read articles referenced by julien. Those algorithms are way better. – Vanuan Sep 11 '14 at 10:22
  • But nobody so far has an answer (besides mine) with a simple explanation of any algorithm that doesn't involve rasterization. – Vanuan Sep 11 '14 at 10:29
  • @radouxju I do not want to interpolate height, and yes, I want to find the median line of each lane. – Vanuan Sep 11 '14 at 10:32
7
+50

Yes, there are such algorithms (see for example here, there and here) but since you seem to have only one single road, would it not be easier to do it by hand? (!). Using for example QGIS, you could import your GPS traces, create a new layer, digitalise the centerline of the bundle, and then export it in whatever format.

Improve this answer
  • It is already digital. You mean I should rasterize it first? I'm a bit worried that I would lost precision by rasterizing. I think the algorithm should take into account the error of each measured point. And I have hundreds of those tracks, so doing it by hand would be quite tedious. I want an algorithm, not "how to do it in Foo Application". Thanks for the links, they look promising. – Vanuan Sep 10 '14 at 16:44
  • Sorry, I'm not into GIS jargon. Could you give an explanation of "digitalise the centerline of the bundle" process? Google doesn't help. – Vanuan Sep 10 '14 at 17:06
  • 1
    Yet another link: mapconstruction.org/#et_page_7 – Vanuan Sep 11 '14 at 0:53
  • youtube.com/watch?v=byJzKjCta3c – Vanuan Sep 11 '14 at 1:23
3

Have you seen this Q&A? You should upload an image and explain your data a bit more, for example are the tracks:

  • Vertices that make up the track regularly sampled distances or do they vary with time?
  • Has the data been truncated to some area of interest or do they just randomly start/stop?
  • What GIS system and license level are you using?

I would imagine there are several ways of doing this, one method comes to mind is to rasterize the tracks and add the grids together, cells with the highest value are where tracks most agree. I'm sure someone will offer up a better approach?

EDIT:

  1. Take each gpx track and convert them into a spatial dataset such as a shapefile with each shapefile containing a single polyline.
  2. Convert this polyline into a raster dataset. The cells that represent the line are given a value of 1 in a background of zeros. Do this for all layers.
  3. Add the rasters together and the pixels with the highest value are where the tracks most coincide.

This can be done in QGIS but you would need to look into that as I do not use that software. Also you'll need to experiment on cell size, too small and nothing overlaps, too big then all tracks will coincide.

Improve this answer
  • 1. Vertices vary with time. 2. No, the data is not truncated, it's basically a loop. 3. I'm not using any GIS system. Hm... This probably should go to StackOverflow then, right? Here's a sample track openstreetmap.org/user/Vanuan/traces/1789135 – Vanuan Sep 9 '14 at 17:05
  • Can you elaborate on rasterizing, adding grids and what is highest value? Are these some GIS system builtin functionality? Say, is it possible to do in QGIS? – Vanuan Sep 9 '14 at 18:04
  • Since vertices change from track to track, rasterising is a valid and relatively simple approach. This answer should be accepted. – Luís de Sousa Sep 10 '14 at 8:37
  • @Hornbydd Thanks for your edit. Now this algorithm has a clear explanation. – Vanuan Sep 10 '14 at 17:04
  • I would add the fourth and fifth steps: filter out cells with lowest value and vectorize the line back. – Vanuan Sep 10 '14 at 17:12
1

After several days of head-scratching I came up with this strategy:

  1. Calculate direction of motion at each point.

calc_angle

For each point:

  1. Filter out points before current (leave only points in the semispace in the direction of motion).

enter image description here

  1. Filter out points that belong to opposite route (leave only points approximately in the same direction)

enter image description here

  1. Remove current from the list, mark as visited

  2. Set the nearest unvisited point as a current and goto 2.

After loop connect/interpolate points in the order of visit.

Simplify track using GPSBabel.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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