| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Linq; |
| | | 4 | | using System.Runtime.CompilerServices; |
| | | 5 | | using System.Threading; |
| | | 6 | | using System.Threading.Tasks; |
| | | 7 | | using Itinero.MapMatching.Model; |
| | | 8 | | using Itinero.MapMatching.Solver; |
| | | 9 | | using Itinero.Network; |
| | | 10 | | using Itinero.Profiles; |
| | | 11 | | using Itinero.Routes.Paths; |
| | | 12 | | using Itinero.Routing; |
| | | 13 | | |
| | | 14 | | [assembly: InternalsVisibleTo("Itinero.MapMatching.Tests")] |
| | | 15 | | [assembly: InternalsVisibleTo("Itinero.MapMatching.Tests.Functional")] |
| | | 16 | | |
| | | 17 | | namespace Itinero.MapMatching; |
| | | 18 | | |
| | | 19 | | /// <summary> |
| | | 20 | | /// The map matcher. |
| | | 21 | | /// </summary> |
| | | 22 | | public class MapMatcher |
| | | 23 | | { |
| | | 24 | | private readonly RoutingNetwork _routingNetwork; |
| | | 25 | | private readonly Profile _profile; |
| | | 26 | | private readonly ModelBuilder _modelBuilder; |
| | | 27 | | private readonly ModelSolver _modelSolver; |
| | | 28 | | |
| | | 29 | | /// <summary> |
| | | 30 | | /// Creates a new map matcher. |
| | | 31 | | /// </summary> |
| | | 32 | | /// <param name="routingNetwork">The routing network.</param> |
| | | 33 | | /// <param name="settings">The settings.</param> |
| | | 34 | | /// <exception cref="Exception"></exception> |
| | 22 | 35 | | public MapMatcher(RoutingNetwork routingNetwork, MapMatcherSettings settings) |
| | 22 | 36 | | { |
| | 22 | 37 | | this.Settings = settings; |
| | 22 | 38 | | _routingNetwork = routingNetwork; |
| | 44 | 39 | | _profile = settings.Profile ?? throw new Exception("No profile set"); ; |
| | | 40 | | |
| | 22 | 41 | | _modelBuilder = new ModelBuilder(routingNetwork, settings.ModelBuilderSettings); |
| | 22 | 42 | | _modelSolver = new ModelSolver(); |
| | 22 | 43 | | } |
| | | 44 | | |
| | | 45 | | /// <summary> |
| | | 46 | | /// The settings. |
| | | 47 | | /// </summary> |
| | 70 | 48 | | public MapMatcherSettings Settings { get; } |
| | | 49 | | |
| | | 50 | | /// <summary> |
| | | 51 | | /// Gets the routing network. |
| | | 52 | | /// </summary> |
| | 24 | 53 | | public RoutingNetwork RoutingNetwork => _routingNetwork; |
| | | 54 | | |
| | | 55 | | /// <summary> |
| | | 56 | | /// Matches the given track. |
| | | 57 | | /// </summary> |
| | | 58 | | /// <param name="track">The track.</param> |
| | | 59 | | /// <param name="cancellationToken">The cancellation token.</param> |
| | | 60 | | /// <returns>One or more matched segments.</returns> |
| | | 61 | | /// <exception cref="Exception"></exception> |
| | | 62 | | public async Task<IEnumerable<MapMatch>> MatchAsync(Track track, CancellationToken cancellationToken = default) |
| | 22 | 63 | | { |
| | 22 | 64 | | var matches = new List<MapMatch>(); |
| | | 65 | | |
| | | 66 | | // build track model. |
| | 22 | 67 | | var trackModels = await _modelBuilder.BuildModels(track, _profile, cancellationToken); |
| | | 68 | | |
| | 118 | 69 | | foreach (var trackModel in trackModels) |
| | 26 | 70 | | { |
| | | 71 | | // run solver. |
| | 26 | 72 | | var bestMatch = _modelSolver.Solve(trackModel).ToList(); |
| | 26 | 73 | | if (cancellationToken.IsCancellationRequested) return ArraySegment<MapMatch>.Empty; |
| | | 74 | | |
| | | 75 | | // calculate the paths between each matched point pair. |
| | 26 | 76 | | var rawPaths = new List<Path>(); |
| | 4112 | 77 | | for (var l = 2; l < bestMatch.Count - 1; l++) |
| | 2030 | 78 | | { |
| | 2030 | 79 | | if (cancellationToken.IsCancellationRequested) return ArraySegment<MapMatch>.Empty; |
| | | 80 | | |
| | 2030 | 81 | | var sourceNodeId = bestMatch[l - 1]; |
| | 2030 | 82 | | var targetNodeId = bestMatch[l]; |
| | 2030 | 83 | | var sourceNode = trackModel.GetNode(sourceNodeId); |
| | 2030 | 84 | | var targetNode = trackModel.GetNode(targetNodeId); |
| | 2030 | 85 | | var source = sourceNode.SnapPoint; |
| | 2030 | 86 | | var target = targetNode.SnapPoint; |
| | | 87 | | |
| | 2030 | 88 | | if (source == null) throw new Exception("Track point should have a snap point"); |
| | 2030 | 89 | | if (target == null) throw new Exception("Track point should have a snap point"); |
| | | 90 | | |
| | | 91 | | // try to use the cached path from model building. |
| | 2030 | 92 | | var edge = trackModel.GetEdge(sourceNodeId, targetNodeId); |
| | 2030 | 93 | | if (edge?.CachedPath != null) |
| | 1992 | 94 | | { |
| | 1992 | 95 | | rawPaths.Add(edge.CachedPath); |
| | 1992 | 96 | | } |
| | | 97 | | else |
| | 38 | 98 | | { |
| | | 99 | | // fallback: re-route if no cached path (e.g. same snap point). |
| | 38 | 100 | | var path = await _routingNetwork.Route(new RoutingSettings() { Profile = _profile }) |
| | 38 | 101 | | .From(source.Value).To(target.Value).PathAsync(CancellationToken.None); |
| | 38 | 102 | | if (path.IsError) |
| | 0 | 103 | | throw new Exception( |
| | 0 | 104 | | $"Raw path calculation failed, it shouldn't fail at this point because it succeeded on the s |
| | 38 | 105 | | rawPaths.Add(path); |
| | 38 | 106 | | } |
| | 2030 | 107 | | } |
| | | 108 | | |
| | | 109 | | // Collect the track point indices from the bestMatch sequence. |
| | | 110 | | // bestMatch[0] is a virtual start node, bestMatch[last] is a virtual end node. |
| | | 111 | | // The real matched nodes are bestMatch[1] through bestMatch[Count-2]. |
| | 26 | 112 | | var trackPointIndices = new List<int>(); |
| | 4164 | 113 | | for (var l = 1; l < bestMatch.Count - 1; l++) |
| | 2056 | 114 | | { |
| | 2056 | 115 | | trackPointIndices.Add(trackModel.GetNode(bestMatch[l]).TrackPoint!.Value); |
| | 2056 | 116 | | } |
| | | 117 | | |
| | 26 | 118 | | matches.Add(new MapMatch(track, _profile, rawPaths, trackPointIndices)); |
| | 26 | 119 | | } |
| | | 120 | | |
| | 22 | 121 | | return matches; |
| | 22 | 122 | | } |
| | | 123 | | } |