Sandwych.MapMatchingKit

Sandwych.MapMatchingKit is a GPS map-matching solution for .NET platform.

This library is ported from the Barefoot project which developed in Java.

What Is Map-Matching?

Map matching is the problem of how to match recorded geographic coordinates to a logical model of the real world, typically using some form of Geographic Information System. The most common approach is to take recorded, serial location points (e.g. from GPS) and relate them to edges in an existing street graph (network), usually in a sorted list representing the travel of a user or vehicle. Matching observations to a logical model in this way has applications in satellite navigation, GPS tracking of freight, and transportation engineering.

Additional Utilities:

Sandwych.Hmm: A general purpose utility library implements Hidden Markov Models (HMM) for time-inhomogeneous Markov processes for .NET.

Roadmap and Current Status

Alpha - Basic functions works.

The API can and will change frequently, do not use it for production.

Getting Started

Prerequisites

Microsoft Visual Studio 2017: This project is written in C# 7.2 using Microsoft Visual Studio 2017 Community Edition Version 15.5.
DocFX to generate API documents (Optional)

Supported Platform

.NET Standard 1.6
.NET Framework 4.5

Installation

Sandwych.MapMatchingKit can be installed from NuGet.

Prepare Your Data

Road Map

Field	Type	Description
Id	long	The unique ID of road line
Source	long	Starting vertex ID of the road line
Target	long	Ending vertex ID of the road line
Oneway	bool	Indicates the road is a one way road or not
Oneway	bool	Indicates the road is a one way road or not
Type	short	Indicates the type of the road (Optional)
Priority	float	Road priority factor, which is greater or equal than one (default is 1.0)
MaxForwardSpeed	float	Maximum speed limit for passing this road from source to target (default is 120.0km/h)
MaxBackwardSpeed	float	Maximum speed limit for passing this road from target to source (default is 120.0km/h)
Length	float	Length of road geometry in meters, can be computed if not provided
Geometry	ILineString	An object of ILineString to represents the road.

GPS Samples

Field	Type	Description
Id	long	The unique ID of the GPS point
Time	DateTimeOffset	The timestamp of the GPS point
Coordinate	Coordinate2D	Longtitude and latitude of the GPS point

Demo & Usage:

See the directory example/Sandwych.MapMatchingKit.Examples.HelloWorldApp for a fully executable map-matching example.

Offline Map-Matching

var spatial = new GeographySpatialOperation();
var mapBuilder = new RoadMapBuilder(spatial);
var roads = //load your road map
var map = mapBuilder.AddRoads(roads).Build();
var router = new DijkstraRouter<Road, RoadPoint>();
var matcher = new Matcher(map, router, Costs.TimePriorityCost, spatial);
var kstate = new MatcherKState();
//Do the map-matching iteration
foreach (var sample in samples)
{
    var vector = matcher.Execute(kstate.Vector(), kstate.Sample, sample);
    kstate.Update(vector, sample);
}
//Fetching map-matching results and accessing them
var candidatesSequence = kstate.Sequence();
foreach (var cand in candidatesSequence)
{
    var roadId = cand.Point.Edge.RoadInfo.Id; // original road id
    var heading = cand.Point.Edge.Headeing; // heading
    var coord = cand.Point.Coordinate; // GPS position (on the road)
    if (cand.HasTransition)
    {
        var geom = cand.Transition.Route.ToGeometry(); // path geometry(LineString) from last matching candidate
        var edges = cand.Transition.Route.Edges // Road segments between two GPS position
    }
}

Online Map-Matching

// Create initial (empty) state memory
var kstate = new MatcherKState();

// Iterate over sequence (stream) of samples
foreach (var sample in samples)
{
    // Execute matcher with single sample and update state memory
    var vector = kstate.Vector();
    vector = matcher.Execute(vector, kstate.Sample, sample);
    kstate.Update(vector, sample);

    // Access map matching result: estimate for most recent sample
    var estimated = kstate.Estimate();
    Console.WriteLine("RoadID={0}", estimated.Point.Edge.RoadInfo.Id); // The id of the road in your map
}

License

This library is licensed under the Apache 2.0 license.

Contribute

Contributions are always welcome! For bug reports, please create an issue.

For code contributions (e.g. new features or bugfixes), please create a pull request.

Credits

All honors belongs to the original Barefoot developed by BMW Car IT GmbH: https://github.com/bmwcarit/barefoot

"hmm-lib" from BMW Car IT GmbH: https://github.com/bmwcarit/hmm-lib
"GeographicLib" from Charles Karney: https://github.com/oldrev/GeographicLib
"Nito.Collections.Deque" from Stephen Cleary: https://github.com/StephenCleary/Deque
"NetTopologySuite & ProjNET4GeoAPI" from NetTopologySuite Project: https://github.com/NetTopologySuite
PriorityQueue class from Rx.NET Project: https://github.com/Reactive-Extensions/Rx.NET
The UBODT(upper-bounded origin destination table) algroithm from Can Yang: https://github.com/cyang-kth/fmm
RBush - The R-Tree spatial index implementation from viceroypenguin: https://github.com/viceroypenguin/RBush
QuickGraph from Peli: https://github.com/oldrev/Sandwych.QuickGraph

oldrev/mapmatchingkit