Quick facts


  • Improves the path one step at a time
  • Leverages the Strava global heatmap
  • Runs server side and is written in Go
  • Most slides complete in under 0.3 seconds

This work was presented at State of the Map US 2014.       video (15 min) - slides

Algorithm overview


The high level idea behind Slide is to let the input line fall (or slide) into the valleys of a surface. The surface is built from GPS data where high density regions are lower, creating valleys along the high density corridors.

the surface visualized

One can imagine a coarse input "string of beads" being placed on the surface and letting gravity pull it downward. When movement stops, the string should follow the valleys.


Details

To mimic the flexibility of a "string of beads," or something similar, the input line is resampled. This allows the discretely sampled line to still behave like a naturally flexible object.

This resampled line is then ran through a loop where each vertex or point is corrected based on a cost function. This cost function has 3 main parts:

  • Depth with respect to the surface
  • Equal distance between resampled points
  • Maximize vertex angles
The components are weighted with the surface getting the most. The other parts are to ensure the line doesn't collapse in on itself and maintains some sense of rigidity.

To speed conversion of the process, a momentum component is added. 20% of the correction from the previous loop is added in.

Once the process converges, the line is simplified again and sent back as the result.


Potential improvement

This work is still young so there are many things left to try and improve. There are the basic things like improving the cost function weightings.

I'd also like to improve the last simplification step as sometimes the result can contain a few unnecessary points, after a visual inspection. Currently it uses a simple Douglas–Peucker algorithm but there are more advanced methods that could solve the issues.

Also, the current algorithm doesn't move endpoints and can result in some weird stuff near the ends. Letting them move freely probably isn't the answer so some other approach needs to be found.

slide algorithm flowchart

Source code


While still under development, source code is available at github.com/paulmach/slide. Contributions welcome. Slide also makes use of go.geo, a geo/geometry library written in Go.

The source for the iD Editor integration is available on Github. If you're interesting in integrating Slide with a different editor, send an email to paul -at- strava.com