< Summary

Class:Itinero.Snapping.Snapper
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Snapping/Snapper.cs
Covered lines:157
Uncovered lines:55
Coverable lines:212
Total lines:401
Line coverage:74% (157 of 212)
Covered branches:75
Total branches:114
Branch coverage:65.7% (75 of 114)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%4100%
ToAsync()29.16%2440.81%
ToAsync()0%60%
ToAsync()100%14100%
ExpandSchedule()100%8100%
ToAllAsync()100%2100%
ToVertexAsync()50%4100%
ToAllVerticesAsync()0%20%
IsAcceptable(...)80%3081.25%
Itinero.Network.Search.Edges.IEdgeChecker.IsAcceptable(...)100%1100%
IsEdgeOnIslandInRequest(...)50%6100%
Itinero-Network-Search-Edges-IEdgeChecker-RunCheckAsync()78.57%14100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Snapping/Snapper.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Linq;
 4using System.Runtime.CompilerServices;
 5using System.Threading;
 6using System.Threading.Tasks;
 7using Itinero.Geo;
 8using Itinero.Network;
 9using Itinero.Network.Enumerators.Edges;
 10using Itinero.Network.Search.Edges;
 11using Itinero.Network.Search.Islands;
 12using Itinero.Profiles;
 13using Itinero.Routing.Costs;
 14
 15namespace Itinero.Snapping;
 16
 17/// <summary>
 18/// Just like the `Snapper`, it'll snap to a location.
 19/// However, the 'Snapper' will match to any road whereas the `LocationSnapper` will only snap to roads accessible to th
 20/// </summary>
 21internal sealed class Snapper : ISnapper, IEdgeChecker
 22{
 23    private readonly RoutingNetwork _routingNetwork;
 24    private readonly bool _anyProfile;
 25    private readonly bool _checkCanStopOn;
 26    private readonly double _offsetInMeter;
 27    private readonly double _offsetInMeterMax;
 28    private readonly double _maxDistance;
 29    private readonly Islands[] _islands;
 30    private readonly ICostFunction[] _costFunctions;
 31    private readonly Profile[] _profiles;
 32
 33    // One directed-graph pair per profile, for the lifetime of this snapper
 34    private readonly IslandDirectedGraph?[] _islandDgFull;
 35    private readonly IslandDirectedGraph?[] _islandDgNonLocal;
 36
 37    // Whether a candidate has to be connected to the wider network, or only usable by the
 38    // profile. Off means access and can-stop-on still apply but nothing asks where the edge
 39    // leads — the caller has taken that question on itself.
 40    private readonly bool _checkConnectivity;
 41
 23642    public Snapper(RoutingNetwork routingNetwork, IEnumerable<Profile> profiles, SnapperSettings settings)
 23643    {
 23644        _routingNetwork = routingNetwork;
 23645        _anyProfile = settings.AnyProfile;
 23646        _checkCanStopOn = settings.CheckCanStopOn;
 23647        _offsetInMeter = settings.OffsetInMeter;
 23648        _offsetInMeterMax = settings.OffsetInMeterMax;
 23649        _maxDistance = settings.MaxDistance;
 23650        _checkConnectivity = settings.CheckIslands;
 23651        _profiles = profiles.ToArray();
 52
 23653        _costFunctions = _profiles.Select(_routingNetwork.GetCostFunctionFor).ToArray();
 23654        _islands = !_checkConnectivity || routingNetwork.IslandManager.MaxIslandSize == 0
 23655            ? []
 24456            : _profiles.Select(p => _routingNetwork.IslandManager.GetIslandsFor(p)).ToArray();
 23657        _islandDgFull = new IslandDirectedGraph?[_profiles.Length];
 23658        _islandDgNonLocal = new IslandDirectedGraph?[_profiles.Length];
 23659    }
 60
 61    /// <inheritdoc/>
 62    public async IAsyncEnumerable<Result<SnapPoint>> ToAsync(VertexId vertexId, bool asDeparture = true)
 5963    {
 5964        var enumerator = _routingNetwork.GetEdgeEnumerator();
 5965        RoutingNetworkEdgeEnumerator? secondEnumerator = null;
 66
 5967        if (!enumerator.MoveTo(vertexId))
 168        {
 169            yield break;
 70        }
 71
 6272        while (enumerator.MoveNext())
 5973        {
 5974            if (_costFunctions.Length == 0)
 5975            {
 5976                if (enumerator.Forward)
 3277                {
 3278                    yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0));
 279                }
 80                else
 2781                {
 2782                    yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue));
 283                }
 484            }
 85            else
 086            {
 087                if (asDeparture)
 088                {
 089                    if (!(this.IsAcceptable(enumerator) ?? await (this as IEdgeChecker).RunCheckAsync(enumerator, defaul
 090                    {
 91
 092                        continue;
 93                    }
 94
 095                    if (enumerator.Forward)
 096                    {
 097                        yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0));
 098                    }
 99                    else
 0100                    {
 0101                        yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue));
 0102                    }
 0103                }
 104                else
 0105                {
 0106                    secondEnumerator ??= _routingNetwork.GetEdgeEnumerator();
 0107                    secondEnumerator.MoveTo(enumerator.EdgeId, !enumerator.Forward);
 0108                    if (!(this.IsAcceptable(secondEnumerator) ?? await (this as IEdgeChecker).RunCheckAsync(secondEnumer
 0109                    {
 0110                        continue;
 111                    }
 112
 0113                    if (enumerator.Forward)
 0114                    {
 0115                        yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0));
 0116                    }
 117                    else
 0118                    {
 0119                        yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue));
 0120                    }
 0121                }
 0122            }
 4123        }
 59124    }
 125
 126    /// <inheritdoc/>
 127    public async Task<Result<SnapPoint>> ToAsync(EdgeId edgeId, ushort offset, bool forward = true)
 0128    {
 0129        var enumerator = _routingNetwork.GetEdgeEnumerator();
 130
 0131        if (!enumerator.MoveTo(edgeId, forward)) return new Result<SnapPoint>("Edge not found");
 132
 0133        if (!(this.IsAcceptable(enumerator) ?? await (this as IEdgeChecker).RunCheckAsync(enumerator, default)))
 0134            return new Result<SnapPoint>("Edge cannot be snapped to by configured profiles in the given direction");
 135
 0136        return new Result<SnapPoint>(new SnapPoint(edgeId, offset));
 0137    }
 138
 139    /// <inheritdoc/>
 140    public async Task<Result<SnapPoint>> ToAsync(
 141        double longitude, double latitude,
 142        CancellationToken cancellationToken = default)
 110143    {
 110144        (double longitude, double latitude, float? e) location = (longitude, latitude, null);
 145
 146        // First load region.
 110147        var box = location.BoxAround(_offsetInMeter);
 110148        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 149
 150        // Iterate over the MaxDistance schedule (50, 200, 800, …, MaxDistance).
 151        // Most snaps land on the first small-D pass; sparse-area / no-snap
 152        // cases escalate through the schedule. PR2's tile + vertex predicates
 153        // make small-D passes nearly free because almost every tile in the
 154        // load box is excluded.
 458155        foreach (var d in ExpandSchedule(_maxDistance))
 116156        {
 116157            var snapPoint = await _routingNetwork.SnapInBoxAsync(box, this, maxDistance: d, cancellationToken);
 220158            if (snapPoint.EdgeId != EdgeId.Empty) return snapPoint;
 12159            if (cancellationToken.IsCancellationRequested) break;
 12160        }
 161
 162        // Retry once with a larger load region — same role as today.
 6163        if (!(_offsetInMeter < _offsetInMeterMax))
 2164        {
 2165            return new Result<SnapPoint>(
 2166                FormattableString.Invariant($"Could not snap to location: {location.longitude},{location.latitude}"));
 167        }
 168
 4169        box = location.BoxAround(_offsetInMeterMax);
 4170        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 171
 24172        foreach (var d in ExpandSchedule(_maxDistance))
 7173        {
 7174            var snapPoint = await _routingNetwork.SnapInBoxAsync(box, this, maxDistance: d, cancellationToken);
 9175            if (snapPoint.EdgeId != EdgeId.Empty) return snapPoint;
 5176            if (cancellationToken.IsCancellationRequested) break;
 5177        }
 178
 2179        return new Result<SnapPoint>(
 2180             FormattableString.Invariant($"Could not snap to location: {location.longitude},{location.latitude}"));
 110181    }
 182
 183    /// <summary>
 184    /// Iterative MaxDistance schedule: start at 50 m, ×4 per step, cap the
 185    /// growth at 10 km (so an unbounded MaxDistance doesn't produce an
 186    /// unbounded schedule), and always end with <paramref name="maxDistance"/>
 187    /// as the final entry. See snap-iterative-cutoff.md for the design.
 188    ///
 189    /// Examples:
 190    ///   maxDistance = ∞      → 50, 200, 800, 3200, 12800, ∞
 191    ///   maxDistance = 1 000  → 50, 200, 800, 1000
 192    ///   maxDistance = 100    → 50, 100
 193    ///   maxDistance = 30     → 30  (single iteration, no growth)
 194    /// </summary>
 195    private static IEnumerable<double> ExpandSchedule(double maxDistance)
 114196    {
 197        const double start = 50.0;
 198        const double growthFactor = 4.0;
 199        const double growthCap = 10_000.0;
 200
 114201        if (maxDistance <= start)
 1202        {
 1203            yield return maxDistance;
 1204            yield break;
 205        }
 206
 113207        var d = start;
 113208        yield return d;
 16209        while (d < maxDistance && d < growthCap)
 9210        {
 9211            d *= growthFactor;
 11212            if (d < maxDistance) yield return d;
 8213        }
 7214        yield return maxDistance;
 7215    }
 216
 217    /// <inheritdoc/>
 218    public async IAsyncEnumerable<SnapPoint> ToAllAsync(double longitude, double latitude, [EnumeratorCancellation] Canc
 2108219    {
 220        // calculate one box for all locations.
 2108221        (double longitude, double latitude, float? e) location = (longitude, latitude, null);
 2108222        var box = location.BoxAround(_offsetInMeter);
 223
 224        // make sure data is loaded.
 2108225        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 226
 227        // snap all.
 2108228        var snapped = _routingNetwork.SnapAllInBoxAsync(box, this, maxDistance: _maxDistance, cancellationToken: cancell
 69590229        await foreach (var snapPoint in snapped)
 31633230        {
 31633231            yield return snapPoint;
 31633232        }
 2108233    }
 234
 235    /// <inheritdoc/>
 236    public async Task<Result<VertexId>> ToVertexAsync(double longitude, double latitude, CancellationToken cancellationT
 1237    {
 1238        (double longitude, double latitude, float? e) location = (longitude, latitude, null);
 239
 240        // calculate one box for all locations.
 1241        var box = location.BoxAround(_maxDistance);
 242
 243        // make sure data is loaded.
 1244        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 245
 246        // snap to closest vertex.
 1247        var vertex = await _routingNetwork.SnapToVertexInBoxAsync(box, _costFunctions.Length > 0 ? this : null, maxDista
 1248        if (vertex.IsEmpty()) return new Result<VertexId>("No vertex in range found");
 249
 1250        return vertex;
 1251    }
 252
 253    /// <inheritdoc/>
 254    public async IAsyncEnumerable<VertexId> ToAllVerticesAsync(double longitude, double latitude,
 255        [EnumeratorCancellation] CancellationToken cancellationToken = default)
 0256    {
 0257        (double longitude, double latitude, float? e) location = (longitude, latitude, null);
 258
 259        // calculate one box for all locations.
 0260        var box = location.BoxAround(_maxDistance);
 261
 262        // make sure data is loaded.
 0263        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 264
 265        // snap to closest vertex.
 0266        await foreach (var vertex in _routingNetwork.SnapToAllVerticesInBoxAsync(box, this,
 0267                     maxDistance: _maxDistance, cancellationToken: cancellationToken))
 0268        {
 0269            yield return vertex;
 0270        }
 0271    }
 272
 273    private bool? IsAcceptable(IEdgeEnumerator<RoutingNetwork> edgeEnumerator)
 57752274    {
 57752275        var hasProfiles = _costFunctions.Length > 0;
 57800276        if (!hasProfiles) return true;
 277
 57704278        var allOk = true;
 230802279        for (var p = 0; p < _costFunctions.Length; p++)
 57704280        {
 57704281            var costFunction = _costFunctions[p];
 282
 283            // check if the edge can be used in either direction.
 284            // both directions need to be checked here because SnapAllInBoxAsync
 285            // deduplicates by EdgeId: a one-way edge first encountered from its
 286            // head vertex would be rejected if only the tail-to-head direction is checked.
 57704287            var costs = costFunction.Get(edgeEnumerator, true, []);
 57704288            var costsReverse = costFunction.Get(edgeEnumerator, false, []);
 289
 290            // if edge is not accessible in either direction, skip it.
 57704291            if (!costs.canAccess && !costsReverse.canAccess)
 25947292            {
 25947293                allOk = false;
 25947294                continue;
 295            }
 296
 297            // check if needed if the edge can be stopped on (in either direction).
 31757298            if (_checkCanStopOn)
 31694299            {
 31694300                if (!costs.canStop && !costsReverse.canStop)
 0301                {
 0302                    allOk = false;
 0303                    continue;
 304                }
 31694305            }
 306
 307            // check if the edge is on an island.
 31757308            if (_checkConnectivity && _islands.Length > 0)
 15309            {
 15310                var tailTileId = edgeEnumerator.Forward ? edgeEnumerator.Tail.TileId : edgeEnumerator.Head.TileId;
 15311                var islands = _islands[p];
 312
 313                // fast path: if the tile is fully done, just check _islandEdges.
 15314                if (islands.GetTileDone(tailTileId))
 8315                {
 8316                    if (islands.IsEdgeOnIsland(edgeEnumerator.EdgeId))
 1317                    {
 1318                        allOk = false;
 1319                        continue;
 320                    }
 321                    // tile done + not in island set → not island.
 7322                }
 323                else
 7324                {
 325                    // Tile not done — ask this request's own graph, which is the only
 326                    // thing that can answer "not an island" for an unfinished tile.
 7327                    var onIsland = this.IsEdgeOnIslandInRequest(p, edgeEnumerator.EdgeId);
 7328                    if (onIsland == true)
 0329                    {
 0330                        allOk = false;
 0331                        continue;
 332                    }
 333
 7334                    if (onIsland == false)
 0335                    {
 336                        // confirmed not island.
 0337                    }
 338                    else
 7339                    {
 340                        // not yet resolved — return null to trigger async resolution.
 7341                        return null;
 342                    }
 0343                }
 7344            }
 345
 346            // any profile is good for a positive result.
 31749347            if (_anyProfile) return true;
 31749348        }
 349
 57697350        return allOk;
 57752351    }
 352
 353    bool? IEdgeChecker.IsAcceptable(IEdgeEnumerator<RoutingNetwork> edgeEnumerator)
 57752354    {
 57752355        return this.IsAcceptable(edgeEnumerator);
 57752356    }
 357
 358    /// <summary>
 359    /// Island verdict from state this request owns: the durable set says island, this
 360    /// request's graph says not-island, otherwise unknown and the caller resolves.
 361    /// </summary>
 362    private bool? IsEdgeOnIslandInRequest(int profileIndex, EdgeId edgeId)
 7363    {
 7364        if (_islands[profileIndex].IsEdgeOnIsland(edgeId)) return true;
 365
 366        // No graph yet means nothing has been classified in this request,
 367        // do not create one just to ask.
 7368        var dg = _islandDgFull[profileIndex];
 7369        if (dg != null && dg.IsNotIsland(edgeId)) return false;
 370
 7371        return null;
 7372    }
 373
 374    async Task<bool> IEdgeChecker.RunCheckAsync(IEdgeEnumerator<RoutingNetwork> edgeEnumerator, CancellationToken cancel
 7375    {
 376        // Nothing to resolve: without a connectivity question IsAcceptable never returns null,
 377        // so arriving here at all means the answer is already in.
 7378        if (!_checkConnectivity) return (this as IEdgeChecker).IsAcceptable(edgeEnumerator) ?? true;
 379
 380        // Build the edge's tile first so every traversable edge in the tile
 381        // gets a definitive Island / NotIsland verdict via ClassifyAsync.
 382        // Subsequent snap candidates in the same tile then short-circuit on
 383        // the per-profile Islands set / dg fast-paths. The IslandManager
 384        // deduplicates concurrent builds for the same (profile, tile).
 7385        var tailTileId = edgeEnumerator.Forward ? edgeEnumerator.Tail.TileId : edgeEnumerator.Head.TileId;
 24386        for (var p = 0; p < _profiles.Length; p++)
 7387        {
 7388            var profile = _profiles[p];
 7389            await _routingNetwork.IslandManager.BuildForTileAsync(_routingNetwork, profile, tailTileId,
 7390                _islandDgFull[p] ??= new IslandDirectedGraph(),
 7391                _islandDgNonLocal[p] ??= new IslandDirectedGraph(), cancellationToken);
 7392            if (cancellationToken.IsCancellationRequested) return true;
 393
 7394            var islands = _routingNetwork.IslandManager.GetIslandsFor(profile);
 9395            if (islands.IsEdgeOnIsland(edgeEnumerator.EdgeId)) return false;
 396            // tile DONE + not in Islands set → NotIsland → acceptable for this profile.
 5397        }
 398
 5399        return (this as IEdgeChecker).IsAcceptable(edgeEnumerator) ?? true;
 7400    }
 401}