Vector to Raster Map Conflation
Go
Switch branches/tags
Nothing to show
Clone or download
paulmach Merge pull request #5 from fhk/master
Update link and add video of presentation
Latest commit 40e05f8 Aug 15, 2017
Permalink
Failed to load latest commit information.
examples/tiger
reducers
surfacers
utils
LICENSE.md
README.md
refine.go
slide.go
surfacer.go

README.md

Slide: Vector to Raster Map Conflation

Slide is an algorithm/approach for conflating vector data with raster data. The idea is to take a coarse approximation to the raster data and have the algorithm slide the polyline to the "image." The result is a properly sampled vector polyline matching the contours of the raster data.

The algorithm is presented as a Go (golang) library. The examples directory has some example integrations. Most of the heavy geometry stuff is done with go.geo, a go geography/geometry library.

Demos

Slide supports the concept of surfacers that can be based on any datasource.

Background

Slide was first developed as a tool to slide Open Street Map map geometry to the Strava Global Heatmap dataset. The 200,000,000,000 Strava GPS points were bucketed by pixel to create the heatmap and essentially creating a raster like density distribution of GPS data. For more information take a look at the links below:

Slide Animation


**Above:** The black polyline is being "slided" to the green path, matching the Strava global heatmap data. Red lines are the intermediate steps of the refinement.

Algorithm Overview

At a high level, Slide works by modeling an input line, or string, sliding into the valleys of a surface. The surface can be built from any datasource.

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 (smooth parametric derivative)
  • Maximize vertex angles (smooth parametric second derivative)

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 where a fraction 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.

Slide Algorithm Overview

Potential improvement

Many! There are the basic things like improving the cost function weightings as well as more challenging things such as incorporating more information from the input data, such as direction. I'd also like to support the sliding of more complex goemetries, such as a road grid.

Related Work

As they say, "There is nothing new under the sun."