< Summary

Class:Itinero.Network.Search.Edges.EdgeSearch
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Edges/EdgeSearch.cs
Covered lines:374
Uncovered lines:36
Coverable lines:410
Total lines:803
Line coverage:91.2% (374 of 410)
Covered branches:262
Total branches:300
Branch coverage:87.3% (262 of 300)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
SnapInBoxAsync()88.88%1896%
NearestCandidatesAsync()81.25%1695%
get_EdgeId()100%1100%
ScanNearestEdges(...)98.57%70100%
Insert(...)92.85%1488.23%
SnapAllInBoxAsync()95.31%64100%
SnapToVertexInBoxAsync()41.66%1268%
SnapToAllVerticesInBoxAsync()0%120%
SearchEdgesInBox(...)100%1100%
EdgeBboxCanBeat(...)100%30100%
TileCanReach(...)100%20100%
VertexCanReach(...)100%12100%
TilesInRing()100%22100%
SafeDelta(...)50%2100%
ClosestBoxDistanceMeters(...)0%80%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Edges/EdgeSearch.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.Enumerators.Edges;
 9using Itinero.Network.Tiles;
 10using Itinero.Snapping;
 11
 12namespace Itinero.Network.Search.Edges;
 13
 14internal static class EdgeSearch
 15{
 16    /// <summary>
 17    /// Returns the closest acceptable edge to the center of the given box that has at least one vertex inside the given
 18    /// </summary>
 19    /// <param name="network">The network.</param>
 20    /// <param name="searchBox">The box to search in.</param>
 21    /// <param name="maxDistance">The maximum distance of any snap point returned relative to the center of the search b
 22    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 23    /// <param name="cancellationToken">The cancellation token.</param>
 24    /// <returns>The closest acceptable edge to the center of the box inside the given box.</returns>
 25    /// <remarks>
 26    /// Geometry first, acceptability second: the old single pass asked the checker on every
 27    /// transient best, which is free for an island lookup and not for a bounded expansion.
 28    /// </remarks>
 29    public static async Task<SnapPoint> SnapInBoxAsync(this RoutingNetwork network,
 30        ((double longitude, double, float? e) topLeft, (double longitude, double latitude, float? e) bottomRight)
 31            searchBox,
 32        IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, CancellationToken cancellationToken = de
 12733    {
 12734        if (edgeChecker == null)
 435        {
 36            // Nothing can be rejected, so the nearest edge is the answer and one is all we need.
 437            var nearest = ScanNearestEdges(network, searchBox, maxDistance, null, 1);
 438            return nearest.Count == 0
 439                ? new SnapPoint(EdgeId.Empty, ushort.MaxValue)
 440                : new SnapPoint(nearest[0].EdgeId, nearest[0].Offset);
 41        }
 42
 12343        var edgeEnumerator = network.GetEdgeEnumerator();
 12344        HashSet<EdgeId>? rejected = null;
 45
 46        // Paged, so a location ringed by unusable edges still finds the road behind them.
 47        // Re-scanning is pure geometry and costs less than a page's worth of checks.
 12348        while (true)
 12349        {
 12350            var page = ScanNearestEdges(network, searchBox, maxDistance, rejected, CandidatePageSize);
 13451            if (page.Count == 0) break;
 52
 45853            foreach (var candidate in page)
 11454            {
 11455                if (!edgeEnumerator.MoveTo(candidate.EdgeId, true)) continue;
 56
 11457                var acceptable = edgeChecker.IsAcceptable(edgeEnumerator)
 11458                                 ?? await edgeChecker.RunCheckAsync(edgeEnumerator, cancellationToken);
 22059                if (acceptable) return new SnapPoint(candidate.EdgeId, candidate.Offset);
 60
 861                (rejected ??= new HashSet<EdgeId>()).Add(candidate.EdgeId);
 862            }
 63
 64            // A short page means the scan ran out of edges, not that this page was unlucky.
 1265            if (page.Count < CandidatePageSize) break;
 066        }
 67
 1768        return new SnapPoint(EdgeId.Empty, ushort.MaxValue);
 12769    }
 70
 71    /// <summary>
 72    /// The acceptable snap candidates, nearest first, until the search box runs out.
 73    /// </summary>
 74    /// <remarks>
 75    /// Lazy and uncapped: a location ringed by footpaths a car cannot use needs however many it
 76    /// takes to reach the road behind them, and a cap reads as "nothing connected near here".
 77    /// </remarks>
 78    /// <remarks>
 79    /// The checker should answer about the edge itself, not where it leads — that is the
 80    /// caller's job, and the reason it wanted candidates one at a time.
 81    /// </remarks>
 82    public static async IAsyncEnumerable<SnapPoint> NearestCandidatesAsync(this RoutingNetwork network,
 83        ((double longitude, double, float? e) topLeft, (double longitude, double latitude, float? e) bottomRight)
 84            searchBox,
 85        IEdgeChecker? edgeChecker, double maxDistance,
 86        [EnumeratorCancellation] CancellationToken cancellationToken = default)
 5687    {
 5688        var edgeEnumerator = network.GetEdgeEnumerator();
 5689        HashSet<EdgeId>? offered = null;
 90
 5691        while (true)
 5692        {
 5693            cancellationToken.ThrowIfCancellationRequested();
 94
 5695            var page = ScanNearestEdges(network, searchBox, maxDistance, offered, CandidatePageSize);
 5696            if (page.Count == 0) yield break;
 97
 22998            foreach (var candidate in page)
 5899            {
 58100                (offered ??= []).Add(candidate.EdgeId);
 101
 58102                if (!edgeEnumerator.MoveTo(candidate.EdgeId, true)) continue;
 103
 58104                var acceptable = edgeChecker == null ||
 58105                                 (edgeChecker.IsAcceptable(edgeEnumerator) ??
 58106                                  await edgeChecker.RunCheckAsync(edgeEnumerator, cancellationToken));
 116107                if (acceptable) yield return new SnapPoint(candidate.EdgeId, candidate.Offset);
 3108            }
 109
 110            // A short page means the scan ran out of edges, not that this page was unlucky.
 2111            if (page.Count < CandidatePageSize) yield break;
 0112        }
 56113    }
 114
 115    /// <summary>
 116    /// How many candidates one scan collects. Small because the first is almost always the
 117    /// answer; more than one only so that a rejection does not cost a whole new scan.
 118    /// </summary>
 119    private const int CandidatePageSize = 16;
 120
 9045121    private readonly record struct EdgeCandidate(EdgeId EdgeId, ushort Offset, double Distance);
 122
 123    /// <summary>
 124    /// The nearest <paramref name="take"/> edges to the centre of the box, nearest first,
 125    /// skipping <paramref name="exclude"/>. Pure geometry — no acceptability, no async, no
 126    /// network beyond the tiles the box covers.
 127    /// </summary>
 128    private static List<EdgeCandidate> ScanNearestEdges(RoutingNetwork network,
 129        ((double longitude, double, float? e) topLeft, (double longitude, double latitude, float? e) bottomRight)
 130            searchBox,
 131        double maxDistance, HashSet<EdgeId>? exclude, int take)
 183132    {
 183133        var center = ((double longitude, double latitude, float? e))searchBox.Center();
 183134        var zoom = network.Zoom;
 135
 136        const double exactTolerance = 1;
 183137        var found = new List<EdgeCandidate>(take);
 138
 139        // The pruning cutoff. With a single candidate this is the old shrinking best; with
 140        // several it can only shrink once the list is full, so the scan prunes less early —
 141        // the price of having a second choice at all.
 183142        var cutoff = maxDistance;
 143
 144        // Spiral tile iteration: start at the tile containing Q, expand to
 145        // ring 1 (8 neighbours), ring 2, ..., until rings fall outside the
 146        // search box. Closest-first ordering means the list fills fast
 147        // and the cutoff shrinks early, so outer-ring tiles get rejected
 148        // by the per-tile predicate before we ever read their edges. Diff
 149        // computation is lazy per-tile, so cold-path snaps avoid touching
 150        // tiles the inner-ring candidates already made irrelevant.
 151
 152        // Search box tile-range bounds (clamped, can be a single tile). The
 153        // searchBox.topLeft's latitude field is unnamed in the parameter
 154        // signature (legacy quirk), so we access it positionally as Item2.
 183155        var tlTile = TileStatic.WorldToTile(searchBox.topLeft.longitude, searchBox.topLeft.Item2, zoom);
 183156        var brTile = TileStatic.WorldToTile(searchBox.bottomRight.longitude, searchBox.bottomRight.latitude, zoom);
 366157        var minX = tlTile.x; var maxX = brTile.x;
 366158        var minY = tlTile.y; var maxY = brTile.y;
 159
 160        // Start tile = Q's tile. Outermost ring needed = max distance from
 161        // start to any corner of the box, in tile units.
 183162        var centerTile = TileStatic.WorldToTile(center.longitude, center.latitude, zoom);
 183163        var cx = centerTile.x;
 183164        var cy = centerTile.y;
 183165        var maxRing = (uint)Math.Max(
 183166            Math.Max(SafeDelta(cx, minX), SafeDelta(maxX, cx)),
 183167            Math.Max(SafeDelta(cy, minY), SafeDelta(maxY, cy)));
 168
 183169        var edgeEnumerator = network.GetEdgeEnumerator();
 170
 824171        for (uint ring = 0; ring <= maxRing; ring++)
 230172        {
 231173            if (cutoff <= 0) break;
 174
 1789175            foreach (var (x, y) in TilesInRing(cx, cy, ring))
 551176            {
 551177                if (cutoff <= 0) break;
 854178                if (x < minX || x > maxX || y < minY || y > maxY) continue;
 179
 248180                var tileId = TileStatic.ToLocalId(x, y, zoom);
 248181                var tile = network.GetTileForRead(tileId);
 277182                if (tile == null) continue;
 219183                tile.EnsureDiffs(network);  // lazy — only for tiles we actually visit
 219184                var bbox = TileStatic.GetTileBoundingBox(zoom, tileId);
 219185                if (!TileCanReach(bbox, tile.MaxLonDiff, tile.MaxLatDiff, center, cutoff)) continue;
 186
 219187                var tileMaxLonDiff = tile.MaxLonDiff;
 219188                var tileMaxLatDiff = tile.MaxLatDiff;
 189
 6326190                for (uint v = 0; v < tile.VertexCount; v++)
 2946191                {
 2948192                    if (cutoff <= 0) break;
 2944193                    var vertexId = new VertexId(tileId, v);
 2944194                    if (!network.TryGetVertex(vertexId, out var vLon, out var vLat, out var vE)) continue;
 195
 196                    // Restore the PR1 candidate set: vertices inside the search
 197                    // box. Without this, we'd walk every vertex in every tile
 198                    // overlapping the box — including those geometrically outside
 199                    // the box. Under cutoff = ∞ (initial state with
 200                    // MaxDistance = ∞) the VertexCanReach predicate is a no-op,
 201                    // so without this check we visit ~40% more vertices than PR1
 202                    // did, paying the per-edge bbox iteration cost for each.
 5273203                    if (!searchBox.Overlaps((vLon, vLat, vE))) continue;
 204
 205                    // Per-vertex predicate: an edge from this vertex extends at
 206                    // most (tileMaxLonDiff, tileMaxLatDiff) in each axis, so if
 207                    // the vertex itself is too far for even that envelope to
 208                    // reach the current cutoff, every edge from it is irrelevant.
 619209                    if (!VertexCanReach(vLon, vLat, tileMaxLonDiff, tileMaxLatDiff, center, cutoff)) continue;
 210
 611211                    if (!edgeEnumerator.MoveTo(vertexId)) continue;
 212
 1864213                    while (edgeEnumerator.MoveNext())
 1253214                    {
 1253215                        if (cutoff <= 0) break;
 1253216                        if (exclude != null && exclude.Contains(edgeEnumerator.EdgeId)) continue;
 217
 218                        // PR1: per-edge MBR prefilter. After the tile and vertex
 219                        // predicates above, only edges that *might* beat the
 220                        // current cutoff reach this point — but the bbox prefilter
 221                        // is still useful to skip edges whose tight bbox can't
 222                        // beat it even though their vertex passed the looser
 223                        // (per-tile-extent) check.
 1431224                        if (!EdgeBboxCanBeat(edgeEnumerator, center, cutoff)) continue;
 225
 226                        // On the edge's own terms: the walk has to finish anyway to know the
 227                        // edge's length, so the cutoff only decides whether to keep the result.
 1075228                        var localDistance = double.MaxValue;
 1075229                        var localOffsetLength = 0.0;
 1075230                        var length = 0.0;
 1075231                        var completeShape = edgeEnumerator.GetCompleteShape();
 1075232                        using (var completeShapeEnumerator = completeShape.GetEnumerator())
 1075233                        {
 1075234                            completeShapeEnumerator.MoveNext();
 1075235                            var previous = completeShapeEnumerator.Current;
 236
 237                            // start with the first location.
 1075238                            var distance = previous.DistanceEstimateInMeter(center);
 1075239                            if (distance < localDistance)
 1075240                            {
 241                                // Rounded here, not at the end: 1e-9 is an exact vertex hit but
 242                                // still looks beatable, and the offset drifts off 0.
 1075243                                localDistance = distance < exactTolerance ? 0 : distance;
 1075244                                localOffsetLength = 0;
 1075245                            }
 246
 247                            // loop over all pairs.
 2336248                            while (completeShapeEnumerator.MoveNext())
 1261249                            {
 1261250                                var current = completeShapeEnumerator.Current;
 251
 1261252                                var segmentLength = previous.DistanceEstimateInMeter(current);
 253
 254                                // first check the actual current location, it may be an exact match.
 1261255                                distance = current.DistanceEstimateInMeter(center);
 1261256                                if (distance < localDistance)
 509257                                {
 509258                                    localDistance = distance < exactTolerance ? 0 : distance;
 509259                                    localOffsetLength = length + segmentLength;
 509260                                }
 261
 262                                // update length.
 1261263                                var startLength = length;
 1261264                                length += segmentLength;
 265
 266                                // project on line segment.
 1261267                                var line = (previous, current);
 1261268                                var originalPrevious = previous;
 1261269                                previous = current;
 1261270                                if (localDistance <= 0)
 283271                                {
 272                                    // we need to continue, we need the total length.
 283273                                    continue;
 274                                }
 275
 978276                                var projected = line.ProjectOn(center);
 978277                                if (!projected.HasValue)
 711278                                {
 711279                                    continue;
 280                                }
 281
 267282                                distance = projected.Value.DistanceEstimateInMeter(center);
 267283                                if (!(distance < localDistance))
 62284                                {
 62285                                    continue;
 286                                }
 287
 205288                                localDistance = distance < exactTolerance ? 0 : distance;
 205289                                localOffsetLength = startLength + originalPrevious.DistanceEstimateInMeter(projected.Val
 205290                            }
 1075291                        }
 292
 1093293                        if (localDistance >= cutoff) continue;
 294
 295                        // calculate the actual offset.
 1057296                        var offset = ushort.MaxValue;
 1057297                        if (localOffsetLength < length)
 678298                        {
 678299                            if (localOffsetLength <= 0)
 518300                            {
 518301                                offset = 0;
 518302                            }
 303                            else
 160304                            {
 160305                                offset = (ushort)(localOffsetLength / length * ushort.MaxValue);
 160306                            }
 678307                        }
 308
 309                        // invert offset if edge is reversed.
 1057310                        if (!edgeEnumerator.Forward)
 524311                        {
 524312                            offset = (ushort)(ushort.MaxValue - offset);
 524313                        }
 314
 1057315                        Insert(found, new EdgeCandidate(edgeEnumerator.EdgeId, offset, localDistance), take);
 1070316                        if (found.Count == take) cutoff = found[take - 1].Distance;
 1057317                    } // while (edgeEnumerator.MoveNext())
 611318                } // for (uint v = 0; v < tile.VertexCount; v++)
 219319            } // foreach (var (x, y) in TilesInRing(...))
 229320        } // for (uint ring = 0; ring <= maxRing; ring++)
 321
 183322        return found;
 183323    }
 324
 325    /// <summary>
 326    /// Inserts into a nearest-first list of at most <paramref name="take"/> entries, replacing
 327    /// the entry for the same edge when it already has one — a vertex's edges are visited from
 328    /// both endpoints, so the same edge can be measured twice.
 329    /// </summary>
 330    private static void Insert(List<EdgeCandidate> found, EdgeCandidate candidate, int take)
 1057331    {
 6576332        for (var i = 0; i < found.Count; i++)
 2688333        {
 4919334            if (found[i].EdgeId != candidate.EdgeId) continue;
 914335            if (found[i].Distance <= candidate.Distance) return;
 336
 0337            found.RemoveAt(i);
 0338            break;
 339        }
 340
 600341        var at = found.Count;
 3026342        for (var i = 0; i < found.Count; i++)
 1084343        {
 1997344            if (!(candidate.Distance < found[i].Distance)) continue;
 345
 171346            at = i;
 171347            break;
 348        }
 349
 600350        if (at >= take) return;
 351
 600352        found.Insert(at, candidate);
 603353        if (found.Count > take) found.RemoveAt(found.Count - 1);
 1057354    }
 355
 356    /// <summary>
 357    /// Snaps all points in the given box that could potentially be snapping points.
 358    /// </summary>
 359    /// <param name="routerDb"></param>
 360    /// <param name="searchBox">The box to search in.</param>
 361    /// <param name="maxDistance">The maximum distance of any snap point returned relative to the center of the search b
 362    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 363    /// <param name="nonOrthogonalEdges">When true the best potential location on each edge is returned, when false only
 364    /// <param name="cancellationToken">The cancellation token.</param>
 365    /// <returns>All edges that could potentially be relevant snapping points, not only the closest.</returns>
 366    public static async IAsyncEnumerable<SnapPoint> SnapAllInBoxAsync(this RoutingNetwork routerDb,
 367        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 368            bottomRight) searchBox,
 369        IEdgeChecker? edgeChecker = null, bool nonOrthogonalEdges = true, double maxDistance = double.MaxValue, Cancella
 2110370    {
 2110371        var edges = new HashSet<EdgeId>();
 2110372        var center = ((double longitude, double latitude, float? e))searchBox.Center();
 2110373        var zoom = routerDb.Zoom;
 374
 375        // Tile-bounded iteration — same structure as SnapInBoxAsync but with
 376        // a fixed maxDistance cutoff (no shrinking-best). Predicates trim
 377        // tiles and vertices that can't possibly contribute any candidate.
 378        // Under unbounded maxDistance they degenerate to "always true" and
 379        // we fall back to the per-edge prefilter alone — same cost as before.
 2110380        var candidates = new List<(uint tileId, NetworkTile tile)>();
 17112381        foreach (var (x, y) in searchBox.TileRange(zoom))
 5391382        {
 5391383            var tileId = TileStatic.ToLocalId(x, y, zoom);
 5391384            var tile = routerDb.GetTileForRead(tileId);
 5481385            if (tile == null) continue;
 5301386            tile.EnsureDiffs(routerDb);  // resolve cross-tile edge endpoints accurately
 5301387            var bbox = TileStatic.GetTileBoundingBox(zoom, tileId);
 5462388            if (!TileCanReach(bbox, tile.MaxLonDiff, tile.MaxLatDiff, center, maxDistance)) continue;
 5140389            candidates.Add((tileId, tile));
 5140390        }
 391
 2110392        var edgeEnumerator = routerDb.GetEdgeEnumerator();
 16610393        foreach (var (tileId, tile) in candidates)
 5140394        {
 5140395            var tileMaxLonDiff = tile.MaxLonDiff;
 5140396            var tileMaxLatDiff = tile.MaxLatDiff;
 397
 5397502398            for (uint v = 0; v < tile.VertexCount; v++)
 2693611399            {
 2693611400                var vertexId = new VertexId(tileId, v);
 2693611401                if (!routerDb.TryGetVertex(vertexId, out var vLon, out var vLat, out var vE)) continue;
 402
 403                // Preserve the historical contract: candidates come from
 404                // vertices inside the search box. Under maxDistance = ∞ the
 405                // VertexCanReach predicate is a no-op, so without this check
 406                // we'd iterate every vertex in every overlapping tile —
 407                // including those geometrically outside the box — and
 408                // measurably regress ToAllAsync_Drain.
 4510246409                if (!searchBox.Overlaps((vLon, vLat, vE))) continue;
 410
 951264411                if (!VertexCanReach(vLon, vLat, tileMaxLonDiff, tileMaxLatDiff, center, maxDistance)) continue;
 412
 802688413                if (!edgeEnumerator.MoveTo(vertexId)) continue;
 3042990414                while (edgeEnumerator.MoveNext())
 2240302415                {
 3317043416                    if (!edges.Add(edgeEnumerator.EdgeId)) continue;
 417
 418                    // PR1 per-edge prefilter — same idea as SnapInBoxAsync.
 419                    // Under maxDistance = ∞ this also degenerates, leaving
 420                    // SnapAllInBoxAsync at same cost as before this PR.
 2266568421                    if (!EdgeBboxCanBeat(edgeEnumerator, center, maxDistance)) continue;
 422
 423                    // search for the best snap point for the current edge.
 60554424                    (EdgeId edgeId, double offset, bool isOrthoganal, double distance) bestEdgeSnapPoint =
 60554425                        (EdgeId.Empty, 0, false, maxDistance);
 60554426                    var isAcceptable = edgeChecker == null ? (bool?)true : null;
 60554427                    var completeShape = edgeEnumerator.GetCompleteShape();
 60554428                    var length = 0.0;
 60554429                    using (var completeShapeEnumerator = completeShape.GetEnumerator())
 60554430                    {
 60554431                        completeShapeEnumerator.MoveNext();
 60554432                        var previous = completeShapeEnumerator.Current;
 433
 434                        // start with the first location.
 60554435                        var distance = previous.DistanceEstimateInMeter(center);
 60554436                        if (distance < bestEdgeSnapPoint.distance)
 48098437                        {
 48098438                            isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsyn
 48098439                            if (!isAcceptable.Value)
 22702440                            {
 22702441                                continue;
 442                            }
 443
 25396444                            bestEdgeSnapPoint = (edgeEnumerator.EdgeId, 0, false, distance);
 25396445                        }
 446
 447                        // loop over all pairs.
 147006448                        while (completeShapeEnumerator.MoveNext())
 112365449                        {
 112365450                            var current = completeShapeEnumerator.Current;
 451
 112365452                            var segmentLength = previous.DistanceEstimateInMeter(current);
 453
 454                            // first check the actual current location, it may be an exact match.
 112365455                            distance = current.DistanceEstimateInMeter(center);
 112365456                            if (distance < bestEdgeSnapPoint.distance)
 32098457                            {
 32098458                                isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheck
 32098459                                if (!isAcceptable.Value)
 3211460                                {
 3211461                                    break;
 462                                }
 463
 28887464                                bestEdgeSnapPoint = (edgeEnumerator.EdgeId, length + segmentLength, false, distance);
 28887465                            }
 466
 467                            // update length.
 109154468                            var startLength = length;
 109154469                            length += segmentLength;
 470
 471                            // project on line segment.
 109154472                            var line = (previous, current);
 109154473                            var originalPrevious = previous;
 109154474                            previous = current;
 475
 109154476                            var projected = line.ProjectOn(center);
 109154477                            if (projected.HasValue)
 8170478                            {
 8170479                                distance = projected.Value.DistanceEstimateInMeter(center);
 8170480                                if (distance < bestEdgeSnapPoint.distance)
 6324481                                {
 6324482                                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunC
 6324483                                    if (isAcceptable.Value)
 6295484                                    {
 6295485                                        bestEdgeSnapPoint = (edgeEnumerator.EdgeId,
 6295486                                            startLength + originalPrevious.DistanceEstimateInMeter(projected.Value),
 6295487                                            true, distance);
 6295488                                    }
 6324489                                }
 8170490                            }
 109154491                        }
 37852492                    }
 493
 494                    // move to the nex edge if no snap point was found.
 37852495                    if (bestEdgeSnapPoint.edgeId == EdgeId.Empty)
 6213496                    {
 6213497                        continue;
 498                    }
 499
 500                    // check type and return if needed.
 31639501                    var returnEdge = bestEdgeSnapPoint.isOrthoganal || nonOrthogonalEdges;
 31639502                    if (!returnEdge)
 1503                    {
 1504                        continue;
 505                    }
 506
 507                    // calculate the actual offset.
 31638508                    var offset = ushort.MaxValue;
 31638509                    if (bestEdgeSnapPoint.offset < length)
 19711510                    {
 19711511                        if (bestEdgeSnapPoint.offset <= 0)
 12778512                        {
 12778513                            offset = 0;
 12778514                        }
 515                        else
 6933516                        {
 6933517                            offset = (ushort)(bestEdgeSnapPoint.offset / length * ushort.MaxValue);
 6933518                        }
 19711519                    }
 520
 521                    // invert offset if edge is reversed.
 31638522                    if (!edgeEnumerator.Forward)
 9629523                    {
 9629524                        offset = (ushort)(ushort.MaxValue - offset);
 9629525                    }
 526
 31638527                    yield return new SnapPoint(bestEdgeSnapPoint.edgeId, offset);
 31638528                } // while (edgeEnumerator.MoveNext())
 802688529            } // for (uint v = 0; v < tile.VertexCount; v++)
 5140530        } // foreach (var (tileId, tile) in candidates)
 2110531    }
 532
 533    /// <summary>
 534    /// Returns the closest vertex to the center of the given box.
 535    /// </summary>
 536    /// <param name="network">The network.</param>
 537    /// <param name="searchBox">The box to search in.</param>
 538    /// <param name="maxDistance">The maximum distance of any vertex returned relative to the center of the search box.<
 539    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 540    /// <param name="cancellationToken">The cancellation token.</param>
 541    /// <returns>The closest edge to the center of the box inside the given box.</returns>
 542    public static async Task<VertexId> SnapToVertexInBoxAsync(this RoutingNetwork network,
 543        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 544            bottomRight) searchBox, IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, Cancellation
 1545    {
 1546        var center = searchBox.Center();
 1547        var closestDistance = maxDistance;
 1548        var closest = VertexId.Empty;
 549
 1550        var vertices = network.SearchVerticesInBox(searchBox);
 1551        var edgeEnumerator = network.GetEdgeEnumerator();
 7552        foreach (var (vertex, location) in vertices)
 2553        {
 2554            var d = center.DistanceEstimateInMeter(location);
 3555            if (d > closestDistance) continue;
 556
 1557            if (edgeChecker == null)
 1558            {
 1559                closest = vertex;
 1560                closestDistance = d;
 1561                continue;
 562            }
 563
 0564            edgeEnumerator.MoveTo(vertex);
 0565            while (edgeEnumerator.MoveNext())
 0566            {
 0567                if (!(edgeChecker.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync(edgeEnumerator, cancel
 568
 0569                closest = vertex;
 0570                closestDistance = d;
 0571                break;
 572            }
 0573        }
 574
 1575        return closest;
 1576    }
 577
 578    /// <summary>
 579    /// Snaps all vertices in the given box that could potentially be snapping vertices.
 580    /// </summary>
 581    /// <param name="network">The network.</param>
 582    /// <param name="searchBox">The box to search in.</param>
 583    /// <param name="maxDistance">The maximum distance of any vertex returned relative to the center of the search box.<
 584    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 585    /// <param name="cancellationToken">The cancellation token.</param>
 586    /// <returns>All the vertices within the box with at least one acceptable edge.</returns>
 587    public static async IAsyncEnumerable<VertexId> SnapToAllVerticesInBoxAsync(this RoutingNetwork network,
 588        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 589            bottomRight) searchBox,
 590        IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, CancellationToken cancellationToken = de
 0591    {
 0592        var center = searchBox.Center();
 0593        var vertices = network.SearchVerticesInBox(searchBox);
 0594        var edgeEnumerator = network.GetEdgeEnumerator();
 0595        foreach (var (vertex, location) in vertices)
 0596        {
 0597            edgeEnumerator.MoveTo(vertex);
 598
 0599            var d = center.DistanceEstimateInMeter(location);
 0600            if (d > maxDistance) continue;
 601
 0602            while (edgeEnumerator.MoveNext())
 0603            {
 0604                if (edgeChecker != null && !(edgeChecker.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync
 605
 0606                yield return vertex;
 0607                break;
 608            }
 0609        }
 0610    }
 611
 612    /// <summary>
 613    /// Enumerates all edges that have at least one vertex in the given bounding box.
 614    /// </summary>
 615    /// <param name="network">The network.</param>
 616    /// <param name="box">The box to enumerate in.</param>
 617    /// <returns>An enumerator with all the vertices and their location.</returns>
 618    public static IEdgeEnumerator<RoutingNetwork> SearchEdgesInBox(this RoutingNetwork network,
 619        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 620            bottomRight) box)
 2621    {
 2622        var vertices = network.SearchVerticesInBox(box);
 4623        return new VertexEdgeEnumerator(network, vertices.Select((i) => i.vertex));
 2624    }
 625
 626    /// <summary>
 627    /// Returns true if the edge's bounding box could possibly produce a snap
 628    /// point closer than <paramref name="bestDistance"/> meters from
 629    /// <paramref name="center"/>. Used as a cheap prefilter before the
 630    /// full per-segment projection loop. Returns false → caller can skip
 631    /// the edge entirely.
 632    ///
 633    /// The bbox is built inline by streaming tail + shape + head once and
 634    /// taking min/max on each axis. Intentionally not cached: a per-tile
 635    /// or per-edge cache costs memory in proportion to graph size, which
 636    /// matters for country/continent-scale router DBs. The per-snap cost
 637    /// is one extra shape iteration per candidate edge, all arithmetic and
 638    /// comparisons, no haversines and no allocations beyond the shape
 639    /// enumerator we'd allocate anyway.
 640    /// </summary>
 641    // Sentinel for "effectively unbounded" cutoffs. Earth's circumference is
 642    // ~4×10⁷ m, so any distance above this threshold can never prune a real
 643    // edge — and importantly catches the very common `double.MaxValue` cutoff
 644    // (which is finite by C# rules and so isn't caught by IsInfinity).
 645    private const double UnboundedDistanceCutoff = 1e10;
 646
 647    private static bool EdgeBboxCanBeat(
 648        IEdgeEnumerator<RoutingNetwork> enumerator,
 649        (double longitude, double latitude, float? e) center,
 650        double bestDistance)
 1164814651    {
 1164824652        if (bestDistance >= UnboundedDistanceCutoff || double.IsNaN(bestDistance)) return true;
 653
 1164804654        var tail = enumerator.TailLocation;
 1164804655        var head = enumerator.HeadLocation;
 1164804656        var minLon = tail.longitude < head.longitude ? tail.longitude : head.longitude;
 1164804657        var maxLon = tail.longitude > head.longitude ? tail.longitude : head.longitude;
 1164804658        var minLat = tail.latitude < head.latitude ? tail.latitude : head.latitude;
 1164804659        var maxLat = tail.latitude > head.latitude ? tail.latitude : head.latitude;
 660
 5909218661        foreach (var (sLon, sLat, _) in enumerator.Shape)
 1207403662        {
 1275291663            if (sLon < minLon) minLon = sLon;
 1199738664            else if (sLon > maxLon) maxLon = sLon;
 1272860665            if (sLat < minLat) minLat = sLat;
 1200059666            else if (sLat > maxLat) maxLat = sLat;
 1207403667        }
 668
 669        // Closest point on the bbox to the query, clamped per axis.
 1164804670        var cLon = center.longitude < minLon ? minLon
 1164804671            : center.longitude > maxLon ? maxLon : center.longitude;
 1164804672        var cLat = center.latitude < minLat ? minLat
 1164804673            : center.latitude > maxLat ? maxLat : center.latitude;
 1164804674        var closest = (cLon, cLat, (float?)null);
 1164804675        return closest.DistanceEstimateInMeter(center) <= bestDistance;
 1164814676    }
 677
 678    /// <summary>
 679    /// Tile-level predicate from snap-algorithm.md. Returns false if no edge
 680    /// with a vertex in this tile can possibly produce a snap within
 681    /// <paramref name="bestDistance"/> of the query, given the tile's own
 682    /// max edge extents.
 683    /// </summary>
 684    private static bool TileCanReach(
 685        (double minLon, double minLat, double maxLon, double maxLat) tileBbox,
 686        double tileMaxLonDiff,
 687        double tileMaxLatDiff,
 688        (double longitude, double latitude, float? e) center,
 689        double bestDistance)
 5520690    {
 5526691        if (bestDistance >= UnboundedDistanceCutoff || double.IsNaN(bestDistance)) return true;
 692
 5514693        var lonClosest = center.longitude < tileBbox.minLon ? tileBbox.minLon
 5514694            : center.longitude > tileBbox.maxLon ? tileBbox.maxLon : center.longitude;
 5514695        var latClosest = center.latitude < tileBbox.minLat ? tileBbox.minLat
 5514696            : center.latitude > tileBbox.maxLat ? tileBbox.maxLat : center.latitude;
 697
 5514698        var dLon = Math.Abs(center.longitude - lonClosest) - tileMaxLonDiff;
 10776699        if (dLon < 0) dLon = 0;
 5514700        var dLat = Math.Abs(center.latitude - latClosest) - tileMaxLatDiff;
 10778701        if (dLat < 0) dLat = 0;
 10621702        if (dLon == 0 && dLat == 0) return true;
 703
 704        // Convert the (dLon, dLat) offset at center.lat into meters by
 705        // measuring the haversine distance from center to a point offset by
 706        // exactly that much. Direction sign doesn't matter for distance.
 407707        var probe = (center.longitude + dLon, center.latitude + dLat, (float?)null);
 407708        return probe.DistanceEstimateInMeter(center) <= bestDistance;
 5520709    }
 710
 711    /// <summary>
 712    /// Per-vertex predicate from snap-algorithm.md. Same shape as
 713    /// <see cref="TileCanReach"/> but the "closest point of the tile bbox"
 714    /// becomes the vertex itself (the actual point, not a clamp).
 715    /// </summary>
 716    private static bool VertexCanReach(
 717        double vLon, double vLat,
 718        double tileMaxLonDiff,
 719        double tileMaxLatDiff,
 720        (double longitude, double latitude, float? e) center,
 721        double bestDistance)
 877591722    {
 877607723        if (bestDistance >= UnboundedDistanceCutoff || double.IsNaN(bestDistance)) return true;
 724
 877575725        var dLon = Math.Abs(center.longitude - vLon) - tileMaxLonDiff;
 1594324726        if (dLon < 0) dLon = 0;
 877575727        var dLat = Math.Abs(center.latitude - vLat) - tileMaxLatDiff;
 1698647728        if (dLat < 0) dLat = 0;
 1559885729        if (dLon == 0 && dLat == 0) return true;
 730
 195265731        var probe = (center.longitude + dLon, center.latitude + dLat, (float?)null);
 195265732        return probe.DistanceEstimateInMeter(center) <= bestDistance;
 877591733    }
 734
 735    /// <summary>
 736    /// Yields the tile coordinates on the perimeter of the square at
 737    /// <paramref name="ring"/> tiles around (<paramref name="cx"/>, <paramref name="cy"/>).
 738    /// Ring 0 is just the centre tile. Tile coords are unsigned, so the
 739    /// caller must filter against valid (in-box) bounds. We compute via
 740    /// <c>long</c> internally to handle the unsigned underflow safely when
 741    /// the centre tile is near (0, 0).
 742    /// </summary>
 743    private static IEnumerable<(uint x, uint y)> TilesInRing(uint cx, uint cy, uint ring)
 229744    {
 229745        if (ring == 0)
 183746        {
 183747            yield return (cx, cy);
 183748            yield break;
 749        }
 750
 46751        var startX = (long)cx - ring;
 46752        var endX = (long)cx + ring;
 46753        var startY = (long)cy - ring;
 46754        var endY = (long)cy + ring;
 755
 756        // Top row (y = startY), full width.
 46757        if (startY >= 0)
 46758        {
 368759            for (var x = startX; x <= endX; x++)
 276760                if (x >= 0) yield return ((uint)x, (uint)startY);
 46761        }
 762
 763        // Right column (x = endX), excluding the top-right corner already yielded.
 276764        for (var y = startY + 1; y <= endY; y++)
 184765            if (y >= 0) yield return ((uint)endX, (uint)y);
 766
 767        // Bottom row (y = endY), right-to-left, excluding the bottom-right corner.
 276768        for (var x = endX - 1; x >= startX; x--)
 184769            if (x >= 0) yield return ((uint)x, (uint)endY);
 770
 771        // Left column (x = startX), bottom-to-top, excluding both corners.
 46772        if (startX >= 0)
 46773        {
 184774            for (var y = endY - 1; y >= startY + 1; y--)
 92775                if (y >= 0) yield return ((uint)startX, (uint)y);
 46776        }
 46777    }
 778
 779    /// <summary>
 780    /// Distance between two unsigned tile indices, returning 0 if the second
 781    /// would underflow the first. Used to size the outermost ring needed to
 782    /// cover the search box without doing signed arithmetic on uints.
 783    /// </summary>
 732784    private static long SafeDelta(uint a, uint b) => a >= b ? (long)(a - b) : 0L;
 785
 786    /// <summary>
 787    /// Used only as a sort key: distance from the query to the tile bbox's
 788    /// closest point, ignoring the tile's max edge extents. Smaller = closer
 789    /// tile, processed first → bestDistance shrinks faster → more aggressive
 790    /// pruning on subsequent tiles.
 791    /// </summary>
 792    private static double ClosestBoxDistanceMeters(
 793        (double minLon, double minLat, double maxLon, double maxLat) bbox,
 794        (double longitude, double latitude, float? e) center)
 0795    {
 0796        var lonClosest = center.longitude < bbox.minLon ? bbox.minLon
 0797            : center.longitude > bbox.maxLon ? bbox.maxLon : center.longitude;
 0798        var latClosest = center.latitude < bbox.minLat ? bbox.minLat
 0799            : center.latitude > bbox.maxLat ? bbox.maxLat : center.latitude;
 0800        var probe = (lonClosest, latClosest, (float?)null);
 0801        return probe.DistanceEstimateInMeter(center);
 0802    }
 803}