slide

README

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.

• Strava Global Heat
  Uses the Strava Global Heatmap to speed map tracing.

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:

• Strava Slide Overview
• Interactive Demo
• OSM iD Editor Integration
• Slide presented at State of the Map US 2014 slides | video.

**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.

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."

• Google correcting Street View sensor data using a nonlinear least squares solver.
• Active Contours, Deformable Models, and Gradient Vector Flow
• Snakes: Active Contour Models, published 1988

Documentation

Index

• Constants
• type Result
• type Slide
  • func New(geometry []*geo.Path, surfacer Surfacer) *Slide
  • func (s *Slide) Do() (*Result, error)
• type SuggestedOptions
• type Surfacer

Constants

const (
	DefaultMinLoops         = 100
	DefaultMaxLoops         = 4000
	DefaultThresholdEpsilon = 0.0005

	DefaultResampleInterval = 5.0 // meters
)

Optimization Parameter defaults

Types

type Result

type Result struct {
	CorrectedGeometry    []*geo.Path
	IntermediateGeometry [][]*geo.Path
	LoopsCompleted       int
	LastLoopError        float64
	LastLoopScore        float64
	Runtime              time.Duration
}

Result is the structure containing the results of the sliding process. Geometries will be paths in lat/lng (EPSG:4326).

type Slide

type Slide struct {
	Geometry   []*geo.Path
	Surfacer   Surfacer
	GeoReducer geo.GeoReducer

	MinLoops   int // will run at least this many refinement steps
	MaxLoops   int // limit on refinement steps
	Goroutines int // concurrency during refinement

	// ThresholdEpsilon is the stop condition used for improvement.
	// See the internal "score" function for more details.
	ThresholdEpsilon float64

	// meters to resample the geometries into before sliding,
	// can impact performance.
	ResampleInterval float64

	// weights for the different components of the cost function.
	GradientScale float64
	DistanceScale float64
	AngleScale    float64
	MomentumScale float64

	// set to the default internal values of gradientContribution, distanceContribution and angleContribution
	// but if you want to get fancy, you can override them.
	GradientContributionFunc func(surfacer Surfacer, point *geo.Point, scale float64) *geo.Point
	DistanceContributionFunc func(path *geo.Path, index int, scale float64) *geo.Point
	AngleContributionFunc    func(path *geo.Path, index int, scale float64) *geo.Point

	// Reduce the correction for paths that are in the valley of the surface.
	// The reduction is based on the original surface value.
	// This option can be helpful when sliding to good data, such as rasterized vector geometry.
	DepthBasedReduction bool

	// NumberIntermediateGeometries is the steps of the refinement processes to save.
	// This is for debugging or animation.
	NumberIntermediateGeometries int
	// contains filtered or unexported fields
}

Slide is the struct that holds all the information to perform a slide.

func New

func New(geometry []*geo.Path, surfacer Surfacer) *Slide

New creates a new Slide structure with the default parameters.

func (*Slide) Do

func (s *Slide) Do() (*Result, error)

Do performs the slide algorithm which includes the following: - transform geometries into EPSG:3857 and resample - iterate and refine path - transform the result back into EPSG:4326

type SuggestedOptions

type SuggestedOptions struct {
	// weights for the different components of the cost function
	GradientScale float64
	DistanceScale float64
	AngleScale    float64
	MomentumScale float64

	// reduce the correction based on surface depth
	DepthBasedReduction bool
}

SuggestedOptions is returned by surfacers to allows them to tell the slide algorithm what the default options should be.

type Surfacer

type Surfacer interface {
	// GradientAt and ValueAt should accept points in the EPSG:3857 (mercator) space.
	GradientAt(point *geo.Point) *geo.Point // typically derived from a smoothed surface
	ValueAt(point *geo.Point) float64       // typically the original surface value (pre smooth)

	// SuggestedOptions allows the surfacer to tell slide what the defaults should be.
	SuggestedOptions() *SuggestedOptions
}

A Surfacer defines what a surface needs to do to be used for sliding. It should define a surface in the mercator projected space (EPSG:3857). Better values should be positive with a maximum of 1 meter, scaled up to be consistent with the EPSG:3857 scaling factor for that latitude.