Create "mean" line from multiple lines using QGIS

Question

I have multiple lines features (also have them in multipoints...) representing similar path (mountain trails, in this case) with various GPS precision, resulting in many lines close to each other, but not perfectly overlapping.

For the purpose of this project, I'm looking for a way to calculate a "mean" line from all of them and generate a resulting line of the most probable position of the trail.

How would you proceed, using QGIS or any other tool (I thought of OGR...)?

Answer 1

Test Data:

• QGIS 2.18.16, GRASS GIS 7
• 4 GPS Tracks
• within a grid of 1x1km

I.)

Create points along your GPS Tracks with the QGIS Plugin Locate Points Along Lines (https://plugins.qgis.org/plugins/LocatePoints/). I've used an interval of 5m in my exmaple.

II.)

Create a Concave Hull with Processing > Toolbox > QGIS geoalgorithms >Vector geometry tools > Concave hull. I used a threshold of 0.1 in my example. If the threshold is to low, there could be holes within the output polygon.

III.)

Now, you can calculate the "mean" line with the help of the skeleton algorithm. Search for skeleton in the Processing Toolbox. Use v.voronoi.skeleton tool from the GRASS GIS 7 commands.

Answer 2

The heat map approach:

The approach is more time consuming, due to the calculating time of the processing steps. It could be seen as an idea maybe to get closer to a more general solution.

Test Data:

• QGIS 2.18.16, GRASS GIS 7
• 4 GPS Tracks
• within a grid of 1x1km

I.)

Create points along your GPS Tracks with the QGIS Plugin Locate Points Along Lines (https://plugins.qgis.org/plugins/LocatePoints/). For the heat map approach I've used an interval of 2m.

II.)

Create a heat map with the QGIS heat map plugin. I've used a radius of 40m. I increase the radius until there are no holes in the output raster. You have to try this with different radius values.

III.)

EDITED There is no need to hold the exact heat map raster value.

Now I want to thin out the raster to the "white" areas, where the most points are concentrated. Therefor I recalculate the output raster. The min/max values of the output raster is 0 and 89.7935. I only use values above 44. Therefor I used a "rule of thumb". Round down the max value and divide it by two. Round down this value another time. 89/2 = 44,5 --> 44. I've used the OSGeo4W Shell: gdal_calc -A heatmap.tif --calc="A>=44" --NoDataValue=0 --outfile=heatmap_44_NoData.tif.

IV.)

EDITED

a) Polygonize the recalculated heat map with Raster > Conversion > Polygonize ...

b) Simplify the polygon Vector > Geometry Tools > Simplify geometries. I've used a tolerance of 2. A simpler polygon reduces the processing time for the skeletons.

c) Calculate skeletons: search for skeleton in the Processing Toolbox. Use v.voronoi.skeleton tool from the GRASS GIS 7 commands.

You can see that the resulting line represents more the most probable position of the trail than in my first answer. Especially for the bend in the North the mean line follows the three tracks which are more close to each other. The same for the bend in the East.

Advantages of the approach:

• reasonable good results exclusively using QGIS

Disadvantages:

• processing time for big data sets
• you have to try parameters a priori (radius of heatmap, min/max values )
• hard to automate the processing steps
• not tested for narrow bends/curves and for tracks which really step out of the line

If someone can optimize the processing steps, your welcome!