< Summary

Class:Itinero.Snapping.Snapper
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Snapping/Snapper.cs
Covered lines:142
Uncovered lines:55
Coverable lines:197
Total lines:364
Line coverage:72% (142 of 197)
Covered branches:62
Total branches:96
Branch coverage:64.5% (62 of 96)
Tag:263_26948838820

Metrics

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

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.Network.Search.Islands;
 13using Itinero.Profiles;
 14using Itinero.Routing.Costs;
 15
 16namespace Itinero.Snapping;
 17
 18/// <summary>
 19/// Just like the `Snapper`, it'll snap to a location.
 20/// However, the 'Snapper' will match to any road whereas the `LocationSnapper` will only snap to roads accessible to th
 21/// </summary>
 22internal sealed class Snapper : ISnapper, IEdgeChecker
 23{
 24    private readonly RoutingNetwork _routingNetwork;
 25    private readonly bool _anyProfile;
 26    private readonly bool _checkCanStopOn;
 27    private readonly double _offsetInMeter;
 28    private readonly double _offsetInMeterMax;
 29    private readonly double _maxDistance;
 30    private readonly Islands[] _islands;
 31    private readonly ICostFunction[] _costFunctions;
 32    private readonly Profile[] _profiles;
 33
 17734    public Snapper(RoutingNetwork routingNetwork, IEnumerable<Profile> profiles, bool anyProfile, bool checkCanStopOn, d
 17735    {
 17736        _routingNetwork = routingNetwork;
 17737        _anyProfile = anyProfile;
 17738        _checkCanStopOn = checkCanStopOn;
 17739        _offsetInMeter = offsetInMeter;
 17740        _offsetInMeterMax = offsetInMeterMax;
 17741        _maxDistance = maxDistance;
 17742        _profiles = profiles.ToArray();
 43
 17744        _costFunctions = _profiles.Select(_routingNetwork.GetCostFunctionFor).ToArray();
 18545        _islands = routingNetwork.IslandManager.MaxIslandSize == 0 ? [] : _profiles.Select(p => _routingNetwork.IslandMa
 17746    }
 47
 48    /// <inheritdoc/>
 49    public async IAsyncEnumerable<Result<SnapPoint>> ToAsync(VertexId vertexId, bool asDeparture = true)
 5950    {
 5951        var enumerator = _routingNetwork.GetEdgeEnumerator();
 5952        RoutingNetworkEdgeEnumerator? secondEnumerator = null;
 53
 5954        if (!enumerator.MoveTo(vertexId))
 155        {
 156            yield break;
 57        }
 58
 6259        while (enumerator.MoveNext())
 5960        {
 5961            if (_costFunctions.Length == 0)
 5962            {
 5963                if (enumerator.Forward)
 3264                {
 3265                    yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0));
 266                }
 67                else
 2768                {
 2769                    yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue));
 270                }
 471            }
 72            else
 073            {
 074                if (asDeparture)
 075                {
 076                    if (!(this.IsAcceptable(enumerator) ?? await (this as IEdgeChecker).RunCheckAsync(enumerator, defaul
 077                    {
 78
 079                        continue;
 80                    }
 81
 082                    if (enumerator.Forward)
 083                    {
 084                        yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0));
 085                    }
 86                    else
 087                    {
 088                        yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue));
 089                    }
 090                }
 91                else
 092                {
 093                    secondEnumerator ??= _routingNetwork.GetEdgeEnumerator();
 094                    secondEnumerator.MoveTo(enumerator.EdgeId, !enumerator.Forward);
 095                    if (!(this.IsAcceptable(secondEnumerator) ?? await (this as IEdgeChecker).RunCheckAsync(secondEnumer
 096                    {
 097                        continue;
 98                    }
 99
 0100                    if (enumerator.Forward)
 0101                    {
 0102                        yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0));
 0103                    }
 104                    else
 0105                    {
 0106                        yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue));
 0107                    }
 0108                }
 0109            }
 4110        }
 59111    }
 112
 113    /// <inheritdoc/>
 114    public async Task<Result<SnapPoint>> ToAsync(EdgeId edgeId, ushort offset, bool forward = true)
 0115    {
 0116        var enumerator = _routingNetwork.GetEdgeEnumerator();
 117
 0118        if (!enumerator.MoveTo(edgeId, forward)) return new Result<SnapPoint>("Edge not found");
 119
 0120        if (!(this.IsAcceptable(enumerator) ?? await (this as IEdgeChecker).RunCheckAsync(enumerator, default)))
 0121            return new Result<SnapPoint>("Edge cannot be snapped to by configured profiles in the given direction");
 122
 0123        return new Result<SnapPoint>(new SnapPoint(edgeId, offset));
 0124    }
 125
 126    /// <inheritdoc/>
 127    public async Task<Result<SnapPoint>> ToAsync(
 128        double longitude, double latitude,
 129        CancellationToken cancellationToken = default)
 79130    {
 79131        (double longitude, double latitude, float? e) location = (longitude, latitude, null);
 132
 133        // First load region.
 79134        var box = location.BoxAround(_offsetInMeter);
 79135        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 136
 137        // Iterate over the MaxDistance schedule (50, 200, 800, …, MaxDistance).
 138        // Most snaps land on the first small-D pass; sparse-area / no-snap
 139        // cases escalate through the schedule. PR2's tile + vertex predicates
 140        // make small-D passes nearly free because almost every tile in the
 141        // load box is excluded.
 334142        foreach (var d in ExpandSchedule(_maxDistance))
 85143        {
 85144            var snapPoint = await _routingNetwork.SnapInBoxAsync(box, this, maxDistance: d, cancellationToken);
 158145            if (snapPoint.EdgeId != EdgeId.Empty) return snapPoint;
 12146            if (cancellationToken.IsCancellationRequested) break;
 12147        }
 148
 149        // Retry once with a larger load region — same role as today.
 6150        if (!(_offsetInMeter < _offsetInMeterMax))
 2151        {
 2152            return new Result<SnapPoint>(
 2153                FormattableString.Invariant($"Could not snap to location: {location.longitude},{location.latitude}"));
 154        }
 155
 4156        box = location.BoxAround(_offsetInMeterMax);
 4157        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 158
 24159        foreach (var d in ExpandSchedule(_maxDistance))
 7160        {
 7161            var snapPoint = await _routingNetwork.SnapInBoxAsync(box, this, maxDistance: d, cancellationToken);
 9162            if (snapPoint.EdgeId != EdgeId.Empty) return snapPoint;
 5163            if (cancellationToken.IsCancellationRequested) break;
 5164        }
 165
 2166        return new Result<SnapPoint>(
 2167             FormattableString.Invariant($"Could not snap to location: {location.longitude},{location.latitude}"));
 79168    }
 169
 170    /// <summary>
 171    /// Iterative MaxDistance schedule: start at 50 m, ×4 per step, cap the
 172    /// growth at 10 km (so an unbounded MaxDistance doesn't produce an
 173    /// unbounded schedule), and always end with <paramref name="maxDistance"/>
 174    /// as the final entry. See snap-iterative-cutoff.md for the design.
 175    ///
 176    /// Examples:
 177    ///   maxDistance = ∞      → 50, 200, 800, 3200, 12800, ∞
 178    ///   maxDistance = 1 000  → 50, 200, 800, 1000
 179    ///   maxDistance = 100    → 50, 100
 180    ///   maxDistance = 30     → 30  (single iteration, no growth)
 181    /// </summary>
 182    private static IEnumerable<double> ExpandSchedule(double maxDistance)
 83183    {
 184        const double start = 50.0;
 185        const double growthFactor = 4.0;
 186        const double growthCap = 10_000.0;
 187
 83188        if (maxDistance <= start)
 1189        {
 1190            yield return maxDistance;
 1191            yield break;
 192        }
 193
 82194        var d = start;
 82195        yield return d;
 16196        while (d < maxDistance && d < growthCap)
 9197        {
 9198            d *= growthFactor;
 11199            if (d < maxDistance) yield return d;
 8200        }
 7201        yield return maxDistance;
 7202    }
 203
 204    /// <inheritdoc/>
 205    public async IAsyncEnumerable<SnapPoint> ToAllAsync(double longitude, double latitude, [EnumeratorCancellation] Canc
 2108206    {
 207        // calculate one box for all locations.
 2108208        (double longitude, double latitude, float? e) location = (longitude, latitude, null);
 2108209        var box = location.BoxAround(_offsetInMeter);
 210
 211        // make sure data is loaded.
 2108212        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 213
 214        // snap all.
 2108215        var snapped = _routingNetwork.SnapAllInBoxAsync(box, this, maxDistance: _maxDistance, cancellationToken: cancell
 69590216        await foreach (var snapPoint in snapped)
 31633217        {
 31633218            yield return snapPoint;
 31633219        }
 2108220    }
 221
 222    /// <inheritdoc/>
 223    public async Task<Result<VertexId>> ToVertexAsync(double longitude, double latitude, CancellationToken cancellationT
 1224    {
 1225        (double longitude, double latitude, float? e) location = (longitude, latitude, null);
 226
 227        // calculate one box for all locations.
 1228        var box = location.BoxAround(_maxDistance);
 229
 230        // make sure data is loaded.
 1231        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 232
 233        // snap to closest vertex.
 1234        var vertex = await _routingNetwork.SnapToVertexInBoxAsync(box, _costFunctions.Length > 0 ? this : null, maxDista
 1235        if (vertex.IsEmpty()) return new Result<VertexId>("No vertex in range found");
 236
 1237        return vertex;
 1238    }
 239
 240    /// <inheritdoc/>
 241    public async IAsyncEnumerable<VertexId> ToAllVerticesAsync(double longitude, double latitude,
 242        [EnumeratorCancellation] CancellationToken cancellationToken = default)
 0243    {
 0244        (double longitude, double latitude, float? e) location = (longitude, latitude, null);
 245
 246        // calculate one box for all locations.
 0247        var box = location.BoxAround(_maxDistance);
 248
 249        // make sure data is loaded.
 0250        await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken);
 251
 252        // snap to closest vertex.
 0253        await foreach (var vertex in _routingNetwork.SnapToAllVerticesInBoxAsync(box, this,
 0254                     maxDistance: _maxDistance, cancellationToken: cancellationToken))
 0255        {
 0256            yield return vertex;
 0257        }
 0258    }
 259
 260    private bool? IsAcceptable(IEdgeEnumerator<RoutingNetwork> edgeEnumerator)
 57671261    {
 57671262        var hasProfiles = _costFunctions.Length > 0;
 57703263        if (!hasProfiles) return true;
 264
 57639265        var allOk = true;
 230542266        for (var p = 0; p < _costFunctions.Length; p++)
 57639267        {
 57639268            var costFunction = _costFunctions[p];
 269
 270            // check if the edge can be used in either direction.
 271            // both directions need to be checked here because SnapAllInBoxAsync
 272            // deduplicates by EdgeId: a one-way edge first encountered from its
 273            // head vertex would be rejected if only the tail-to-head direction is checked.
 57639274            var costs = costFunction.Get(edgeEnumerator, true, []);
 57639275            var costsReverse = costFunction.Get(edgeEnumerator, false, []);
 276
 277            // if edge is not accessible in either direction, skip it.
 57639278            if (!costs.canAccess && !costsReverse.canAccess)
 25952279            {
 25952280                allOk = false;
 25952281                continue;
 282            }
 283
 284            // check if needed if the edge can be stopped on (in either direction).
 31687285            if (_checkCanStopOn)
 31679286            {
 31679287                if (!costs.canStop && !costsReverse.canStop)
 0288                {
 0289                    allOk = false;
 0290                    continue;
 291                }
 31679292            }
 293
 294            // check if the edge is on an island.
 31687295            if (_islands.Length > 0)
 18296            {
 18297                var tailTileId = edgeEnumerator.Forward ? edgeEnumerator.Tail.TileId : edgeEnumerator.Head.TileId;
 18298                var islands = _islands[p];
 299
 300                // fast path: if the tile is fully done, just check _islandEdges.
 18301                if (islands.GetTileDone(tailTileId))
 11302                {
 11303                    if (islands.IsEdgeOnIsland(edgeEnumerator.EdgeId))
 4304                    {
 4305                        allOk = false;
 4306                        continue;
 307                    }
 308                    // tile done + not in island set → not island.
 7309                }
 310                else
 7311                {
 312                    // tile not done — check DG for already resolved edges.
 7313                    var onIsland = _routingNetwork.IslandManager.IsEdgeOnIsland(_profiles[p], edgeEnumerator.EdgeId);
 7314                    if (onIsland == true)
 0315                    {
 0316                        allOk = false;
 0317                        continue;
 318                    }
 319
 7320                    if (onIsland == false)
 0321                    {
 322                        // confirmed not island.
 0323                    }
 324                    else
 7325                    {
 326                        // not yet resolved — return null to trigger async resolution.
 7327                        return null;
 328                    }
 0329                }
 7330            }
 331
 332            // any profile is good for a positive result.
 31676333            if (_anyProfile) return true;
 31676334        }
 335
 57632336        return allOk;
 57671337    }
 338
 339    bool? IEdgeChecker.IsAcceptable(IEdgeEnumerator<RoutingNetwork> edgeEnumerator)
 57671340    {
 57671341        return this.IsAcceptable(edgeEnumerator);
 57671342    }
 343
 344    async Task<bool> IEdgeChecker.RunCheckAsync(IEdgeEnumerator<RoutingNetwork> edgeEnumerator, CancellationToken cancel
 7345    {
 346        // Build the edge's tile first so every traversable edge in the tile
 347        // gets a definitive Island / NotIsland verdict via ClassifyAsync.
 348        // Subsequent snap candidates in the same tile then short-circuit on
 349        // the per-profile Islands set / dg fast-paths. The IslandManager
 350        // deduplicates concurrent builds for the same (profile, tile).
 7351        var tailTileId = edgeEnumerator.Forward ? edgeEnumerator.Tail.TileId : edgeEnumerator.Head.TileId;
 33352        foreach (var profile in _profiles)
 7353        {
 7354            await _routingNetwork.IslandManager.BuildForTileAsync(_routingNetwork, profile, tailTileId, cancellationToke
 7355            if (cancellationToken.IsCancellationRequested) return true;
 356
 7357            var islands = _routingNetwork.IslandManager.GetIslandsFor(profile);
 9358            if (islands.IsEdgeOnIsland(edgeEnumerator.EdgeId)) return false;
 359            // tile DONE + not in Islands set → NotIsland → acceptable for this profile.
 5360        }
 361
 5362        return (this as IEdgeChecker).IsAcceptable(edgeEnumerator) ?? true;
 7363    }
 364}
Generated by: ReportGenerator 4.8.2.0
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
ToAsync()
ToAsync()
ToAsync()
ExpandSchedule()
ToAllAsync()
ToVertexAsync()
ToAllVerticesAsync()
IsAcceptable(...)
Itinero.Network.Search.Edges.IEdgeChecker.IsAcceptable(...)
Itinero-Network-Search-Edges-IEdgeChecker-RunCheckAsync()