# How to compute the outline of multiple tracks?

I have multiple gps tracks with depth data gathered from the lake. The tracks are overlapping/intersecting. I want to get an outline polygon. I have a multi-line shp. I've tried to diffuse it in qgis and buffer. But buffering amounts of data I have simply stalls the PC, after eight hours of work buffer was still processing data.

Is there a simpler and more productive way to get outline from multiple tracks? (Preferably using qgis, gdal, or any other free software)

This is what I have:

This is what I need to get:

Another part of the goal is to preserve the precision of vector data. And hopefully the solution should work for large majority of cases automatically. And it probably shouldn't involve rasterizing image to keep memory use as low as possible.

It should be noted that simple approach to do some kind of approximation causes the solution to be sensible to data. I.e. each data set will have to be treated individually to remove errors related to approximation.

EDIT: Images updated

• alpha shapes / hull Commented Jun 19, 2014 at 12:45
• An alpha hull solution will preserve the precision, but at least in the example provided in this question its memory use will likely be greater than the raster solution (because there are so many vertices used in the collection of tracks and many more have to be created along the track segments). If most of your datasets cover the lakes as densely as this one, you might optimize computing resources by using a moderately coarse raster solution to identify and remove most of the interior track segments and then apply an alpha hull (or other vector based) solution to what remains. Commented Jun 20, 2014 at 15:07
• Not sure about alpha hull but complexity algorithm I implemented mostly depends only on line intersection number. Actually complexity is something like O(k^l), where k is the number of intersections for outline, l is average number of connections per intersection. My unoptimized/rough implementation written in C# in dealt with this data-set (11454 dissolved tracks/1055k points) in several seconds. This is general approach not requiring any adjustment or conversion to other formats.
– alex
Commented Jun 20, 2014 at 15:46
• Using a simple line-sweep algorithm, you should be able to do this in O(n log(n)) effort where n is the number of track segments. Commented Jun 29, 2014 at 20:02

There are two strategies to handle this. One is to replace the tracks by closely spaced sequences of points and then apply the alpha hull techniques suggested in some comments. Perhaps a simple and faster way uses a raster representation (such as the image in the question itself). I will discuss the latter.

A little simplification--perhaps by dilating and eroding the tracks a tiny bit to merge nearby tracks into one and reduce the gaps among them--followed by a region grouping operation (to identify each connected component of the complementary area) will enable all the gaps among the tracks to be selected, particularly the entire surrounding area. The complement of the surrounding area is the desired answer.

The left hand solution results from dilating and eroding the tracks by a circular neighborhood of 5 pixel radius (about 0.7% of the image width). This procedure guarantees that the result will include all portions of the tracks. However, it can leave some empty spaces in the interior where no tracks come close to each other: see the small white circular area left of top center. That area has been removed in the right hand solution, which was created as described above.

Dilation and erosion (and other typical image-cleaning operations) are fast and efficient. Region grouping can take a little more time, depending on how complex the complement of the tracks is: that is one reason to perform the initial simplification.

Image processing software (but not GISes) often provides an "area fill" procedure that will do the trick in one operation: just fill from a point known to be outside the tracks; its complement is the solution.

The gray region shows the area fill (performed with the Windows Paint applet, of all things!). The white and red pixels (which are easily identified, merged, and extracted) collectively are the desired result.

This solution, despite its speed and simplicity, is sometimes not to be recommended, because it is guaranteed to be biased: it will definitely not extend to all portions of the lake's shoreline. (Notice how jagged the boundary appears and compare that with the smoother boundaries in the previous solutions.) The alpha hull or erosion-dilation methods in the previous solutions will expand the lake extent slightly (by an amount under user control), enabling potentially more accurate solutions to be created.

• These are all simplistic approaches ignoring data that is there. I've written a lossless (vector based) algorithm that in essence is similar to convex hull but uses the multi-line data. I'll post it somewhere.
– alex
Commented Jun 20, 2014 at 9:59
• Please indicate which data are "ignored". The solutions and strategies I have outlined have used all the data presented and described in the question. No doubt more could be available--but first you have to describe it. It is very strange that you would attack solutions as "simplistic" that demonstrably meet your stated requirements to be "simpler" and "more productive." If those are not your real requirements, then please edit the question to reflect what you are truly looking for. Commented Jun 20, 2014 at 11:35
• Sorry, didn't want to formulate my comment as verbal attack. My point is that your solution involves rasterization in one way or another. Each map will have to be treated individually - to determine proper resolution, or define other parameter, check if the result is ok and so on. Why bother treat vertices separately and then apply heuristics to locate boundaries again if you have already boundary curves. I was expecting that problem is popular and solution is straight forward. Apparently it's not so I'll reformulate the question.
– alex
Commented Jun 20, 2014 at 14:24
• @aleksas I would like to see your solution as an answer to this interesting problem. Commented Jun 23, 2014 at 7:10
• As soon as I finish demonstration app I'll publish it and post the answer.
– alex
Commented Jun 23, 2014 at 9:30

Solution that works for me best involves picking subset of GPS tracks to construct an outline. For that I've wrote an algorithm that takes dissolved (split at intersection points) tracks set. The algorithm is very simple. It is based on searching for the neighboring track with the smallest angle between intermediate outline end vector and candidate curve(track section after splitting). This algorithms constructs outline after several iterations.

Sourecode in C# and library demo app is available here: github.com (Originaly: outlinefromtracks.codeplex.com)

The first weak point of the algorithm is inability to add already added curve to the path - this causes exclusion of the regions connected by a single curve (rare but important case) and the second weak point is necessity to mark inner curves when there are multiple disconnected regions of curves, it causes to slow overall performance dramatically. First issue could be fixed by allowing to use same curve twice in path (non-trivial) or adding some heuristics detecting those curves and acting appropriately. The second issue could be solved by building initial neighboring curve graph which would also increase outline calculation. Graph construction could be a side product of dissolving initial GPS tracks thus cheap from computing resources perspective.

Look into the 'convex hull' tool, under Vector/Geoprocessing tools. Lets you select an input layer, and a location to save the outline in a seperate shapefile.

• My shapes are concave. Convex hull would not produce what I need.
– alex
Commented Jun 19, 2014 at 12:37
• Googling for 'concave hull qgis' leads to this: inca.coop/news/concave-hull-%E2%80%93-gis-problem-put-bed-last. If you're looking into using Postgis to solve your problem, this might help as well: bostongis.com/postgis_concavehull.snippet Commented Jun 19, 2014 at 12:43
• Treating data as point set not line set will lead to errors. And such approach requires adjustments. Both samples you provide take point set approach. Postgis solution you provided judging from samples provided there would work badly due to shape irregularities (see Neighborhoods sample). The thing with my data is that it's not just a set of points it's a set of tracks. Final true outline is combination of subsets of existing tracks.
– alex
Commented Jun 19, 2014 at 13:11