< Summary

Class:Itinero.MapMatching.Model.ModelBuilder
Assembly:Itinero.MapMatching
File(s):/home/runner/work/routing2/routing2/src/Itinero.MapMatching/Model/ModelBuilder.cs
Covered lines:190
Uncovered lines:2
Coverable lines:192
Total lines:306
Line coverage:98.9% (190 of 192)
Covered branches:65
Total branches:70
Branch coverage:92.8% (65 of 70)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%2100%
BuildModels()83.33%6100%
BuildModel()93.54%6298.79%

File(s)

/home/runner/work/routing2/routing2/src/Itinero.MapMatching/Model/ModelBuilder.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Globalization;
 4using System.Threading;
 5using System.Threading.Tasks;
 6using Itinero.Geo;
 7using Itinero.Network;
 8using Itinero.Profiles;
 9using Itinero.Routes.Paths;
 10using Itinero.Routing;
 11using Itinero.Snapping;
 12
 13namespace Itinero.MapMatching.Model;
 14
 15/// <summary>
 16/// The model builder. Builds an HMM factor graph for map matching using the
 17/// Newson &amp; Krumm (2009) probabilistic model:
 18/// - Emission probability: Gaussian based on GPS noise (sigma_z)
 19/// - Transition probability: Exponential based on |great-circle distance - route distance| (beta)
 20/// </summary>
 21public class ModelBuilder
 22{
 23    private readonly RoutingNetwork _routingNetwork;
 24    private readonly ModelBuilderSettings _settings;
 25
 26    /// <summary>
 27    /// Creates a new model builder.
 28    /// </summary>
 29    /// <param name="routingNetwork">The routing network.</param>
 30    /// <param name="settings">The settings.</param>
 3131    public ModelBuilder(RoutingNetwork routingNetwork, ModelBuilderSettings? settings = null)
 3132    {
 3133        _routingNetwork = routingNetwork;
 3134        _settings = settings ?? new ModelBuilderSettings();
 3135    }
 36
 37    /// <summary>
 38    /// Builds one or more graph models for the given track.
 39    /// </summary>
 40    /// <param name="track">The track.</param>
 41    /// <param name="profile">The profile to match with.</param>
 42    /// <param name="cancellationToken">The cancellation token.</param>
 43    /// <returns>One or more graph models with probabilities as costs.</returns>
 44    public async Task<IEnumerable<GraphModel>> BuildModels(Track track, Profile profile, CancellationToken cancellationT
 3145    {
 3146        var models = new List<GraphModel>();
 47
 3148        var start = 0;
 6849        while (start < track.Count - 1)
 3750        {
 3751            var (model, lastUsed) = await this.BuildModel(track, profile, start, cancellationToken);
 3752            if (cancellationToken.IsCancellationRequested) return ArraySegment<GraphModel>.Empty;
 53
 3754            if (lastUsed == start)
 455            {
 56                // nothing consumed, move next.
 457                start++;
 458                continue;
 59            }
 60
 3361            models.Add(model);
 3362            start = lastUsed;
 3363        }
 64
 3165        return models;
 3166    }
 67
 68    private async Task<(GraphModel model, int index)> BuildModel(Track track, Profile profile, int start, CancellationTo
 3769    {
 3770        var model = new GraphModel(track);
 71
 72        // Newson & Krumm (2009) HMM parameters.
 3773        var sigmaZ = _settings.SigmaZ;
 3774        var beta = _settings.Beta;
 3775        var searchRadius = _settings.SearchRadius;
 3776        var minPointDistance = _settings.MinPointDistance;
 3777        var maxPointSkip = _settings.MaxPointSkip;
 3778        var breakageDistance = _settings.BreakageDistance;
 3779        var maxRouteDistanceFactor = _settings.MaxRouteDistanceFactor;
 80
 81        // precompute for emission cost: 1 / (2 * sigma_z^2)
 3782        var invDoubleSigmaZSq = 1.0 / (2.0 * sigmaZ * sigmaZ);
 83        // precompute for transition cost: 1 / beta
 3784        var invBeta = 1.0 / beta;
 85
 3786        var previousLayer = new List<int>();
 3787        var startNode = new GraphNode();
 3788        previousLayer.Add(model.AddNode(startNode));
 89
 3790        var lastPoint = start;
 3791        var lastUsedLocation = start > 0
 3792            ? (track[start].Location.longitude, track[start].Location.latitude, (float?)null)
 3793            : ((double, double, float?))default;
 3794        var consecutiveSkips = 0;
 95
 96        // use a snap bounding box larger than the search radius
 97        // to account for tile boundaries and long edges in the spatial index.
 3798        var snapBox = Math.Max(searchRadius * 3, 500);
 3799        var snapper = _routingNetwork.Snap(profile, s =>
 37100        {
 37101            s.OffsetInMeter = snapBox;
 37102            s.OffsetInMeterMax = snapBox;
 74103        });
 104
 7002105        for (var i = start; i < track.Count; i++)
 3470106        {
 3470107            var trackPoint = track[i];
 3470108            var trackPointLocation = (trackPoint.Location.longitude, trackPoint.Location.latitude, (float?)null);
 109
 110            // close-point filtering: skip points too close to the last used point.
 3470111            if (i > start && lastUsedLocation != default)
 3433112            {
 3433113                var distToLast = lastUsedLocation.DistanceEstimateInMeter(trackPointLocation);
 114
 115                // breakage distance: if too far, break the model.
 3433116                if (distToLast > breakageDistance)
 1117                {
 1118                    break;
 119                }
 120
 121                // skip points too close together.
 3432122                if (distToLast < minPointDistance)
 1362123                {
 1362124                    continue;
 125                }
 2070126            }
 127
 2107128            var trackPointLayer = new List<int>();
 2107129            var isConnected = false;
 130
 131            // phase 1: collect all snap candidates and add nodes.
 2107132            var currentCandidates = new List<(SnapPoint snapPoint, int nodeId, double emissionCost)>();
 69577133            await foreach (var snapPoint in snapper
 2107134                               .ToAllAsync(trackPointLocation.longitude, trackPointLocation.latitude, cancellationToken:
 31628135            {
 31628136                if (cancellationToken.IsCancellationRequested) return (new GraphModel(track), start);
 137
 31628138                var distanceToCandidate = trackPointLocation.DistanceEstimateInMeter(snapPoint.LocationOnNetwork(_routin
 50301139                if (distanceToCandidate > searchRadius) continue;
 140
 141                // Emission cost: Gaussian model (negative log probability, ignoring normalization constant).
 142                // cost = distance^2 / (2 * sigma_z^2)
 12955143                var emissionCost = distanceToCandidate * distanceToCandidate * invDoubleSigmaZSq;
 144
 145                // add node.
 12955146                var node = new GraphNode() { TrackPoint = i, SnapPoint = snapPoint, Cost = emissionCost };
 12955147                var nodeId = model.AddNode(node);
 12955148                currentCandidates.Add((snapPoint, nodeId, emissionCost));
 12955149            }
 150
 2107151            if (currentCandidates.Count == 0)
 3152            {
 3153                consecutiveSkips++;
 3154                if (consecutiveSkips > maxPointSkip)
 0155                {
 0156                    break;
 157                }
 3158                continue;
 159            }
 160
 161            // great-circle distance between consecutive track points.
 2104162            var greatCircleDistance = 0.0;
 2104163            if (lastPoint > start || i > start)
 2068164            {
 2068165                var previousTrackPoint = track[lastPoint];
 2068166                var previousTrackPointLocation = (previousTrackPoint.Location.longitude,
 2068167                    previousTrackPoint.Location.latitude, (float?)null);
 2068168                greatCircleDistance = previousTrackPointLocation.DistanceEstimateInMeter(trackPointLocation);
 2068169            }
 170
 2104171            var maxRouteDistance = greatCircleDistance * maxRouteDistanceFactor;
 15059172            var targetSnapPoints = currentCandidates.ConvertAll(c => c.snapPoint);
 173
 174            // phase 2: for each previous candidate, route one-to-many to all current candidates.
 2104175            var nodeIsConnected = new bool[currentCandidates.Count];
 28976176            foreach (var previousNode in previousLayer)
 11332177            {
 11332178                var previousSnapPoint = model.GetNode(previousNode).SnapPoint;
 179
 11332180                if (previousSnapPoint == null)
 37181                {
 182                    // start node: connect to all current candidates with zero transition cost.
 368183                    for (var c = 0; c < currentCandidates.Count; c++)
 147184                    {
 147185                        model.AddEdge(new GraphEdge()
 147186                        {
 147187                            Node1 = previousNode,
 147188                            Node2 = currentCandidates[c].nodeId,
 147189                            Cost = 0
 147190                        });
 147191                        isConnected = true;
 147192                        nodeIsConnected[c] = true;
 147193                    }
 37194                    continue;
 195                }
 196
 197                // check for same snap points (zero transition cost).
 11295198                var needsRouting = false;
 397218199                for (var c = 0; c < currentCandidates.Count; c++)
 187314200                {
 187314201                    if (previousSnapPoint.Value.EdgeId == currentCandidates[c].snapPoint.EdgeId &&
 187314202                        previousSnapPoint.Value.Offset == currentCandidates[c].snapPoint.Offset)
 5177203                    {
 5177204                        model.AddEdge(new GraphEdge()
 5177205                        {
 5177206                            Node1 = previousNode,
 5177207                            Node2 = currentCandidates[c].nodeId,
 5177208                            Cost = 0
 5177209                        });
 5177210                        isConnected = true;
 5177211                        nodeIsConnected[c] = true;
 5177212                    }
 213                    else
 182137214                    {
 182137215                        needsRouting = true;
 182137216                    }
 187314217                }
 218
 11297219                if (!needsRouting) continue;
 220
 221                // one-to-many: single Dijkstra from this previous candidate to all current candidates.
 11293222                var paths = await _routingNetwork.Route(new RoutingSettings() { MaxDistance = maxRouteDistance, Profile 
 11293223                    .From(previousSnapPoint.Value).To(targetSnapPoints).Paths(cancellationToken);
 224
 397210225                for (var c = 0; c < currentCandidates.Count; c++)
 187312226                {
 227                    // skip same-snap-point pairs already handled above.
 187312228                    if (previousSnapPoint.Value.EdgeId == currentCandidates[c].snapPoint.EdgeId &&
 187312229                        previousSnapPoint.Value.Offset == currentCandidates[c].snapPoint.Offset)
 5175230                        continue;
 231
 182137232                    var pathResult = paths[c];
 240607233                    if (pathResult.IsError) continue;
 234
 123667235                    var cachedPath = pathResult.Value;
 123667236                    var routeDistance = cachedPath.LengthInMeters();
 237
 238                    // Transition cost: Exponential model (negative log probability).
 239                    // cost = |greatCircleDistance - routeDistance| / beta
 123667240                    var dt = Math.Abs(greatCircleDistance - routeDistance);
 123667241                    var transitionCost = dt * invBeta;
 242
 123667243                    var attributes = new List<(string key, string value)>
 123667244                    {
 123667245                        ("great_circle_distance", greatCircleDistance.ToString(CultureInfo.InvariantCulture)),
 123667246                        ("route_distance", routeDistance.ToString(CultureInfo.InvariantCulture)),
 123667247                        ("dt", dt.ToString(CultureInfo.InvariantCulture))
 123667248                    };
 249
 123667250                    model.AddEdge(new GraphEdge()
 123667251                    {
 123667252                        Node1 = previousNode,
 123667253                        Node2 = currentCandidates[c].nodeId,
 123667254                        Cost = transitionCost,
 123667255                        Attributes = attributes,
 123667256                        CachedPath = cachedPath
 123667257                    });
 123667258                    isConnected = true;
 123667259                    nodeIsConnected[c] = true;
 123667260                }
 11293261            }
 262
 30118263            for (var c = 0; c < currentCandidates.Count; c++)
 12955264            {
 12955265                if (nodeIsConnected[c])
 11312266                {
 11312267                    trackPointLayer.Add(currentCandidates[c].nodeId);
 11312268                }
 12955269            }
 270
 2104271            if (!isConnected)
 29272            {
 273                // try skipping this point before breaking.
 29274                consecutiveSkips++;
 29275                if (consecutiveSkips > maxPointSkip)
 5276                {
 5277                    break;
 278                }
 24279                continue;
 280            }
 281
 282            // successfully matched this point: reset skip counter and advance.
 2075283            consecutiveSkips = 0;
 2075284            previousLayer = trackPointLayer;
 2075285            lastPoint = i;
 2075286            lastUsedLocation = trackPointLocation;
 2075287        }
 288
 37289        var endNode = new GraphNode();
 37290        var endNodeId = model.AddNode(endNode);
 291
 292        // add edges from previous layer to last node.
 309293        foreach (var previousNode in previousLayer)
 99294        {
 99295            model.AddEdge(new GraphEdge()
 99296            {
 99297                Node1 = previousNode,
 99298                Node2 = endNodeId,
 99299                Cost = 0 // last edges have cost 0.
 99300            });
 99301        }
 302
 37303        return (model, lastPoint);
 37304    }
 305
 306}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
BuildModels()
BuildModel()