< 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:339
Uncovered lines:36
Coverable lines:375
Total lines:710
Line coverage:90.4% (339 of 375)
Covered branches:232
Total branches:266
Branch coverage:87.2% (232 of 266)
Tag:263_26948838820

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
SnapInBoxAsync()96.42%8497.14%
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.Threading;
 5using System.Threading.Tasks;
 6using Itinero.Geo;
 7using Itinero.Network.Enumerators.Edges;
 8using Itinero.Network.Tiles;
 9using Itinero.Snapping;
 10
 11namespace Itinero.Network.Search.Edges;
 12
 13internal static class EdgeSearch
 14{
 15    /// <summary>
 16    /// Returns the closest edge to the center of the given box that has at least one vertex inside the given box.
 17    /// </summary>
 18    /// <param name="network">The network.</param>
 19    /// <param name="searchBox">The box to search in.</param>
 20    /// <param name="maxDistance">The maximum distance of any snap point returned relative to the center of the search b
 21    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 22    /// <param name="cancellationToken">The cancellation token.</param>
 23    /// <returns>The closest edge to the center of the box inside the given box.</returns>
 24    public static async Task<SnapPoint> SnapInBoxAsync(this RoutingNetwork network,
 25        ((double longitude, double, float? e) topLeft, (double longitude, double latitude, float? e) bottomRight)
 26            searchBox,
 27        IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, CancellationToken cancellationToken = de
 9628    {
 9629        var center = ((double longitude, double latitude, float? e))searchBox.Center();
 9630        var zoom = network.Zoom;
 31
 32        const double exactTolerance = 1;
 9633        var bestDistance = maxDistance;
 9634        (EdgeId edgeId, ushort offset) bestSnapPoint = (EdgeId.Empty, ushort.MaxValue);
 35
 36        // Spiral tile iteration: start at the tile containing Q, expand to
 37        // ring 1 (8 neighbours), ring 2, ..., until rings fall outside the
 38        // search box. Closest-first ordering means the first snap lands fast
 39        // and bestDistance shrinks early, so outer-ring tiles get rejected
 40        // by the per-tile predicate before we ever read their edges. Diff
 41        // computation is lazy per-tile, so cold-path snaps avoid touching
 42        // tiles the inner-ring snap already made irrelevant.
 43
 44        // Search box tile-range bounds (clamped, can be a single tile). The
 45        // searchBox.topLeft's latitude field is unnamed in the parameter
 46        // signature (legacy quirk), so we access it positionally as Item2.
 9647        var tlTile = TileStatic.WorldToTile(searchBox.topLeft.longitude, searchBox.topLeft.Item2, zoom);
 9648        var brTile = TileStatic.WorldToTile(searchBox.bottomRight.longitude, searchBox.bottomRight.latitude, zoom);
 19249        var minX = tlTile.x; var maxX = brTile.x;
 19250        var minY = tlTile.y; var maxY = brTile.y;
 51
 52        // Start tile = Q's tile. Outermost ring needed = max distance from
 53        // start to any corner of the box, in tile units.
 9654        var centerTile = TileStatic.WorldToTile(center.longitude, center.latitude, zoom);
 9655        var cx = centerTile.x;
 9656        var cy = centerTile.y;
 9657        var maxRing = (uint)Math.Max(
 9658            Math.Max(SafeDelta(cx, minX), SafeDelta(maxX, cx)),
 9659            Math.Max(SafeDelta(cy, minY), SafeDelta(maxY, cy)));
 60
 9661        var edgeEnumerator = network.GetEdgeEnumerator();
 62
 39063        for (uint ring = 0; ring <= maxRing; ring++)
 10264        {
 10565            if (bestDistance <= 0) break;
 66
 53767            foreach (var (x, y) in TilesInRing(cx, cy, ring))
 12068            {
 12069                if (bestDistance <= 0) break;
 13770                if (x < minX || x > maxX || y < minY || y > maxY) continue;
 71
 10372                var tileId = TileStatic.ToLocalId(x, y, zoom);
 10373                var tile = network.GetTileForRead(tileId);
 11474                if (tile == null) continue;
 9275                tile.EnsureDiffs(network);  // lazy — only for tiles we actually visit
 9276                var bbox = TileStatic.GetTileBoundingBox(zoom, tileId);
 9277                if (!TileCanReach(bbox, tile.MaxLonDiff, tile.MaxLatDiff, center, bestDistance)) continue;
 78
 9279                var tileMaxLonDiff = tile.MaxLonDiff;
 9280                var tileMaxLatDiff = tile.MaxLatDiff;
 81
 75482                for (uint v = 0; v < tile.VertexCount; v++)
 34283                {
 39984                    if (bestDistance <= 0) break;
 28585                    var vertexId = new VertexId(tileId, v);
 28586                    if (!network.TryGetVertex(vertexId, out var vLon, out var vLat, out var vE)) continue;
 87
 88                    // Restore the PR1 candidate set: vertices inside the search
 89                    // box. Without this, we'd walk every vertex in every tile
 90                    // overlapping the box — including those geometrically outside
 91                    // the box. Under bestDistance = ∞ (initial state with
 92                    // MaxDistance = ∞) the VertexCanReach predicate is a no-op,
 93                    // so without this check we visit ~40% more vertices than PR1
 94                    // did, paying the per-edge bbox iteration cost for each.
 45395                    if (!searchBox.Overlaps((vLon, vLat, vE))) continue;
 96
 97                    // Per-vertex predicate: an edge from this vertex extends at
 98                    // most (tileMaxLonDiff, tileMaxLatDiff) in each axis, so if
 99                    // the vertex itself is too far for even that envelope to
 100                    // reach the current best, every edge from it is irrelevant.
 124101                    if (!VertexCanReach(vLon, vLat, tileMaxLonDiff, tileMaxLatDiff, center, bestDistance)) continue;
 102
 110103                    if (!edgeEnumerator.MoveTo(vertexId)) continue;
 104
 241105                    while (edgeEnumerator.MoveNext())
 149106                    {
 167107                        if (bestDistance <= 0) break;
 108
 109                        // PR1: per-edge MBR prefilter. After the tile and vertex
 110                        // predicates above, only edges that *might* beat the
 111                        // current best reach this point — but the bbox prefilter
 112                        // is still useful to skip edges whose tight bbox can't
 113                        // beat best even though their vertex passed the looser
 114                        // (per-tile-extent) check.
 153115                        if (!EdgeBboxCanBeat(edgeEnumerator, center, bestDistance)) continue;
 116
 117                        // search for the local snap point that improves the current best snap point.
 109118                        (EdgeId edgeId, double offset) localSnapPoint = (EdgeId.Empty, 0);
 109119                        var isAcceptable = edgeChecker == null ? (bool?)true : null;
 109120                        var completeShape = edgeEnumerator.GetCompleteShape();
 109121                        var length = 0.0;
 109122                        using (var completeShapeEnumerator = completeShape.GetEnumerator())
 109123                        {
 109124                            completeShapeEnumerator.MoveNext();
 109125                            var previous = completeShapeEnumerator.Current;
 126
 127                            // start with the first location.
 109128                            var distance = previous.DistanceEstimateInMeter(center);
 109129                            if (distance < bestDistance)
 67130                            {
 67131                                isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 67132                                                                          await edgeChecker.RunCheckAsync(edgeEnumerator
 67133                                if (!isAcceptable.Value)
 16134                                {
 16135                                    continue;
 136                                }
 137
 51138                                if (distance < exactTolerance)
 44139                                {
 44140                                    distance = 0;
 44141                                }
 142
 51143                                bestDistance = distance;
 51144                                localSnapPoint = (edgeEnumerator.EdgeId, 0);
 51145                            }
 146
 147                            // loop over all pairs.
 231148                            while (completeShapeEnumerator.MoveNext())
 138149                            {
 138150                                var current = completeShapeEnumerator.Current;
 151
 138152                                var segmentLength = previous.DistanceEstimateInMeter(current);
 153
 154                                // first check the actual current location, it may be an exact match.
 138155                                distance = current.DistanceEstimateInMeter(center);
 138156                                if (distance < bestDistance)
 33157                                {
 33158                                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 33159                                                     await edgeChecker.RunCheckAsync(edgeEnumerator, cancellationToken);
 33160                                    if (!isAcceptable.Value)
 0161                                    {
 0162                                        break;
 163                                    }
 164
 33165                                    if (distance < exactTolerance)
 22166                                    {
 22167                                        distance = 0;
 22168                                    }
 169
 33170                                    bestDistance = distance;
 33171                                    localSnapPoint = (edgeEnumerator.EdgeId, length + segmentLength);
 33172                                }
 173
 174                                // update length.
 138175                                var startLength = length;
 138176                                length += segmentLength;
 177
 178                                // TODO: figure this out, there has to be a way to not project every segment.
 179                                //                        // check if we even need to check.
 180                                //                        var previousDistance = previous.DistanceEstimateInMeter(center
 181                                //                        var shapePointDistance = current.DistanceEstimateInMeter(cente
 182                                //                        if (previousDistance + segmentLength > bestDistance &&
 183                                //                            shapePointDistance + segmentLength > bestDistance)
 184                                //                        {
 185                                //                            continue;
 186                                //                        }
 187
 188                                // project on line segment.
 138189                                var line = (previous, current);
 138190                                var originalPrevious = previous;
 138191                                previous = current;
 138192                                if (bestDistance <= 0)
 84193                                {
 194                                    // we need to continue, we need the total length.
 84195                                    continue;
 196                                }
 197
 54198                                var projected = line.ProjectOn(center);
 54199                                if (!projected.HasValue)
 26200                                {
 26201                                    continue;
 202                                }
 203
 28204                                distance = projected.Value.DistanceEstimateInMeter(center);
 28205                                if (!(distance < bestDistance))
 14206                                {
 14207                                    continue;
 208                                }
 209
 14210                                isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 14211                                                 await edgeChecker.RunCheckAsync(edgeEnumerator, cancellationToken);
 14212                                if (!isAcceptable.Value)
 0213                                {
 0214                                    break;
 215                                }
 216
 14217                                if (distance < exactTolerance)
 4218                                {
 4219                                    distance = 0;
 4220                                }
 221
 14222                                bestDistance = distance;
 14223                                localSnapPoint = (edgeEnumerator.EdgeId,
 14224                                    startLength + originalPrevious.DistanceEstimateInMeter(projected.Value));
 14225                            }
 93226                        }
 227
 228                        // move to the nex edge if no better point was found.
 93229                        if (localSnapPoint.edgeId == EdgeId.Empty)
 13230                        {
 13231                            continue;
 232                        }
 233
 234                        // calculate the actual offset.
 80235                        var offset = ushort.MaxValue;
 80236                        if (localSnapPoint.offset < length)
 58237                        {
 58238                            if (localSnapPoint.offset <= 0)
 45239                            {
 45240                                offset = 0;
 45241                            }
 242                            else
 13243                            {
 13244                                offset = (ushort)(localSnapPoint.offset / length * ushort.MaxValue);
 13245                            }
 58246                        }
 247
 248                        // invert offset if edge is reversed.
 80249                        if (!edgeEnumerator.Forward)
 14250                        {
 14251                            offset = (ushort)(ushort.MaxValue - offset);
 14252                        }
 253
 80254                        bestSnapPoint = (localSnapPoint.edgeId, offset);
 80255                    } // while (edgeEnumerator.MoveNext())
 110256                } // for (uint v = 0; v < tile.VertexCount; v++)
 92257            } // foreach (var (x, y) in TilesInRing(...))
 99258        } // for (uint ring = 0; ring <= maxRing; ring++)
 259
 96260        return new SnapPoint(bestSnapPoint.edgeId, bestSnapPoint.offset);
 96261    }
 262
 263    /// <summary>
 264    /// Snaps all points in the given box that could potentially be snapping points.
 265    /// </summary>
 266    /// <param name="routerDb"></param>
 267    /// <param name="searchBox">The box to search in.</param>
 268    /// <param name="maxDistance">The maximum distance of any snap point returned relative to the center of the search b
 269    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 270    /// <param name="nonOrthogonalEdges">When true the best potential location on each edge is returned, when false only
 271    /// <param name="cancellationToken">The cancellation token.</param>
 272    /// <returns>All edges that could potentially be relevant snapping points, not only the closest.</returns>
 273    public static async IAsyncEnumerable<SnapPoint> SnapAllInBoxAsync(this RoutingNetwork routerDb,
 274        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 275            bottomRight) searchBox,
 276        IEdgeChecker? edgeChecker = null, bool nonOrthogonalEdges = true, double maxDistance = double.MaxValue, Cancella
 2110277    {
 2110278        var edges = new HashSet<EdgeId>();
 2110279        var center = ((double longitude, double latitude, float? e))searchBox.Center();
 2110280        var zoom = routerDb.Zoom;
 281
 282        // Tile-bounded iteration — same structure as SnapInBoxAsync but with
 283        // a fixed maxDistance cutoff (no shrinking-best). Predicates trim
 284        // tiles and vertices that can't possibly contribute any candidate.
 285        // Under unbounded maxDistance they degenerate to "always true" and
 286        // we fall back to the per-edge prefilter alone — same cost as before.
 2110287        var candidates = new List<(uint tileId, NetworkTile tile)>();
 17112288        foreach (var (x, y) in searchBox.TileRange(zoom))
 5391289        {
 5391290            var tileId = TileStatic.ToLocalId(x, y, zoom);
 5391291            var tile = routerDb.GetTileForRead(tileId);
 5481292            if (tile == null) continue;
 5301293            tile.EnsureDiffs(routerDb);  // resolve cross-tile edge endpoints accurately
 5301294            var bbox = TileStatic.GetTileBoundingBox(zoom, tileId);
 5462295            if (!TileCanReach(bbox, tile.MaxLonDiff, tile.MaxLatDiff, center, maxDistance)) continue;
 5140296            candidates.Add((tileId, tile));
 5140297        }
 298
 2110299        var edgeEnumerator = routerDb.GetEdgeEnumerator();
 16610300        foreach (var (tileId, tile) in candidates)
 5140301        {
 5140302            var tileMaxLonDiff = tile.MaxLonDiff;
 5140303            var tileMaxLatDiff = tile.MaxLatDiff;
 304
 5397502305            for (uint v = 0; v < tile.VertexCount; v++)
 2693611306            {
 2693611307                var vertexId = new VertexId(tileId, v);
 2693611308                if (!routerDb.TryGetVertex(vertexId, out var vLon, out var vLat, out var vE)) continue;
 309
 310                // Preserve the historical contract: candidates come from
 311                // vertices inside the search box. Under maxDistance = ∞ the
 312                // VertexCanReach predicate is a no-op, so without this check
 313                // we'd iterate every vertex in every overlapping tile —
 314                // including those geometrically outside the box — and
 315                // measurably regress ToAllAsync_Drain.
 4510246316                if (!searchBox.Overlaps((vLon, vLat, vE))) continue;
 317
 951264318                if (!VertexCanReach(vLon, vLat, tileMaxLonDiff, tileMaxLatDiff, center, maxDistance)) continue;
 319
 802688320                if (!edgeEnumerator.MoveTo(vertexId)) continue;
 3042990321                while (edgeEnumerator.MoveNext())
 2240302322                {
 3317043323                    if (!edges.Add(edgeEnumerator.EdgeId)) continue;
 324
 325                    // PR1 per-edge prefilter — same idea as SnapInBoxAsync.
 326                    // Under maxDistance = ∞ this also degenerates, leaving
 327                    // SnapAllInBoxAsync at same cost as before this PR.
 2266568328                    if (!EdgeBboxCanBeat(edgeEnumerator, center, maxDistance)) continue;
 329
 330                    // search for the best snap point for the current edge.
 60554331                    (EdgeId edgeId, double offset, bool isOrthoganal, double distance) bestEdgeSnapPoint =
 60554332                        (EdgeId.Empty, 0, false, maxDistance);
 60554333                    var isAcceptable = edgeChecker == null ? (bool?)true : null;
 60554334                    var completeShape = edgeEnumerator.GetCompleteShape();
 60554335                    var length = 0.0;
 60554336                    using (var completeShapeEnumerator = completeShape.GetEnumerator())
 60554337                    {
 60554338                        completeShapeEnumerator.MoveNext();
 60554339                        var previous = completeShapeEnumerator.Current;
 340
 341                        // start with the first location.
 60554342                        var distance = previous.DistanceEstimateInMeter(center);
 60554343                        if (distance < bestEdgeSnapPoint.distance)
 48098344                        {
 48098345                            isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsyn
 48098346                            if (!isAcceptable.Value)
 22702347                            {
 22702348                                continue;
 349                            }
 350
 25396351                            bestEdgeSnapPoint = (edgeEnumerator.EdgeId, 0, false, distance);
 25396352                        }
 353
 354                        // loop over all pairs.
 147006355                        while (completeShapeEnumerator.MoveNext())
 112365356                        {
 112365357                            var current = completeShapeEnumerator.Current;
 358
 112365359                            var segmentLength = previous.DistanceEstimateInMeter(current);
 360
 361                            // first check the actual current location, it may be an exact match.
 112365362                            distance = current.DistanceEstimateInMeter(center);
 112365363                            if (distance < bestEdgeSnapPoint.distance)
 32098364                            {
 32098365                                isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheck
 32098366                                if (!isAcceptable.Value)
 3211367                                {
 3211368                                    break;
 369                                }
 370
 28887371                                bestEdgeSnapPoint = (edgeEnumerator.EdgeId, length + segmentLength, false, distance);
 28887372                            }
 373
 374                            // update length.
 109154375                            var startLength = length;
 109154376                            length += segmentLength;
 377
 378                            // project on line segment.
 109154379                            var line = (previous, current);
 109154380                            var originalPrevious = previous;
 109154381                            previous = current;
 382
 109154383                            var projected = line.ProjectOn(center);
 109154384                            if (projected.HasValue)
 8170385                            {
 8170386                                distance = projected.Value.DistanceEstimateInMeter(center);
 8170387                                if (distance < bestEdgeSnapPoint.distance)
 6324388                                {
 6324389                                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunC
 6324390                                    if (isAcceptable.Value)
 6295391                                    {
 6295392                                        bestEdgeSnapPoint = (edgeEnumerator.EdgeId,
 6295393                                            startLength + originalPrevious.DistanceEstimateInMeter(projected.Value),
 6295394                                            true, distance);
 6295395                                    }
 6324396                                }
 8170397                            }
 109154398                        }
 37852399                    }
 400
 401                    // move to the nex edge if no snap point was found.
 37852402                    if (bestEdgeSnapPoint.edgeId == EdgeId.Empty)
 6213403                    {
 6213404                        continue;
 405                    }
 406
 407                    // check type and return if needed.
 31639408                    var returnEdge = bestEdgeSnapPoint.isOrthoganal || nonOrthogonalEdges;
 31639409                    if (!returnEdge)
 1410                    {
 1411                        continue;
 412                    }
 413
 414                    // calculate the actual offset.
 31638415                    var offset = ushort.MaxValue;
 31638416                    if (bestEdgeSnapPoint.offset < length)
 19711417                    {
 19711418                        if (bestEdgeSnapPoint.offset <= 0)
 12778419                        {
 12778420                            offset = 0;
 12778421                        }
 422                        else
 6933423                        {
 6933424                            offset = (ushort)(bestEdgeSnapPoint.offset / length * ushort.MaxValue);
 6933425                        }
 19711426                    }
 427
 428                    // invert offset if edge is reversed.
 31638429                    if (!edgeEnumerator.Forward)
 9629430                    {
 9629431                        offset = (ushort)(ushort.MaxValue - offset);
 9629432                    }
 433
 31638434                    yield return new SnapPoint(bestEdgeSnapPoint.edgeId, offset);
 31638435                } // while (edgeEnumerator.MoveNext())
 802688436            } // for (uint v = 0; v < tile.VertexCount; v++)
 5140437        } // foreach (var (tileId, tile) in candidates)
 2110438    }
 439
 440    /// <summary>
 441    /// Returns the closest vertex to the center of the given box.
 442    /// </summary>
 443    /// <param name="network">The network.</param>
 444    /// <param name="searchBox">The box to search in.</param>
 445    /// <param name="maxDistance">The maximum distance of any vertex returned relative to the center of the search box.<
 446    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 447    /// <param name="cancellationToken">The cancellation token.</param>
 448    /// <returns>The closest edge to the center of the box inside the given box.</returns>
 449    public static async Task<VertexId> SnapToVertexInBoxAsync(this RoutingNetwork network,
 450        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 451            bottomRight) searchBox, IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, Cancellation
 1452    {
 1453        var center = searchBox.Center();
 1454        var closestDistance = maxDistance;
 1455        var closest = VertexId.Empty;
 456
 1457        var vertices = network.SearchVerticesInBox(searchBox);
 1458        var edgeEnumerator = network.GetEdgeEnumerator();
 7459        foreach (var (vertex, location) in vertices)
 2460        {
 2461            var d = center.DistanceEstimateInMeter(location);
 3462            if (d > closestDistance) continue;
 463
 1464            if (edgeChecker == null)
 1465            {
 1466                closest = vertex;
 1467                closestDistance = d;
 1468                continue;
 469            }
 470
 0471            edgeEnumerator.MoveTo(vertex);
 0472            while (edgeEnumerator.MoveNext())
 0473            {
 0474                if (!(edgeChecker.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync(edgeEnumerator, cancel
 475
 0476                closest = vertex;
 0477                closestDistance = d;
 0478                break;
 479            }
 0480        }
 481
 1482        return closest;
 1483    }
 484
 485    /// <summary>
 486    /// Snaps all vertices in the given box that could potentially be snapping vertices.
 487    /// </summary>
 488    /// <param name="network">The network.</param>
 489    /// <param name="searchBox">The box to search in.</param>
 490    /// <param name="maxDistance">The maximum distance of any vertex returned relative to the center of the search box.<
 491    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 492    /// <param name="cancellationToken">The cancellation token.</param>
 493    /// <returns>All the vertices within the box with at least one acceptable edge.</returns>
 494    public static async IAsyncEnumerable<VertexId> SnapToAllVerticesInBoxAsync(this RoutingNetwork network,
 495        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 496            bottomRight) searchBox,
 497        IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, CancellationToken cancellationToken = de
 0498    {
 0499        var center = searchBox.Center();
 0500        var vertices = network.SearchVerticesInBox(searchBox);
 0501        var edgeEnumerator = network.GetEdgeEnumerator();
 0502        foreach (var (vertex, location) in vertices)
 0503        {
 0504            edgeEnumerator.MoveTo(vertex);
 505
 0506            var d = center.DistanceEstimateInMeter(location);
 0507            if (d > maxDistance) continue;
 508
 0509            while (edgeEnumerator.MoveNext())
 0510            {
 0511                if (edgeChecker != null && !(edgeChecker.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync
 512
 0513                yield return vertex;
 0514                break;
 515            }
 0516        }
 0517    }
 518
 519    /// <summary>
 520    /// Enumerates all edges that have at least one vertex in the given bounding box.
 521    /// </summary>
 522    /// <param name="network">The network.</param>
 523    /// <param name="box">The box to enumerate in.</param>
 524    /// <returns>An enumerator with all the vertices and their location.</returns>
 525    public static IEdgeEnumerator<RoutingNetwork> SearchEdgesInBox(this RoutingNetwork network,
 526        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 527            bottomRight) box)
 2528    {
 2529        var vertices = network.SearchVerticesInBox(box);
 4530        return new VertexEdgeEnumerator(network, vertices.Select((i) => i.vertex));
 2531    }
 532
 533    /// <summary>
 534    /// Returns true if the edge's bounding box could possibly produce a snap
 535    /// point closer than <paramref name="bestDistance"/> meters from
 536    /// <paramref name="center"/>. Used as a cheap prefilter before the
 537    /// full per-segment projection loop. Returns false → caller can skip
 538    /// the edge entirely.
 539    ///
 540    /// The bbox is built inline by streaming tail + shape + head once and
 541    /// taking min/max on each axis. Intentionally not cached: a per-tile
 542    /// or per-edge cache costs memory in proportion to graph size, which
 543    /// matters for country/continent-scale router DBs. The per-snap cost
 544    /// is one extra shape iteration per candidate edge, all arithmetic and
 545    /// comparisons, no haversines and no allocations beyond the shape
 546    /// enumerator we'd allocate anyway.
 547    /// </summary>
 548    // Sentinel for "effectively unbounded" cutoffs. Earth's circumference is
 549    // ~4×10⁷ m, so any distance above this threshold can never prune a real
 550    // edge — and importantly catches the very common `double.MaxValue` cutoff
 551    // (which is finite by C# rules and so isn't caught by IsInfinity).
 552    private const double UnboundedDistanceCutoff = 1e10;
 553
 554    private static bool EdgeBboxCanBeat(
 555        IEdgeEnumerator<RoutingNetwork> enumerator,
 556        (double longitude, double latitude, float? e) center,
 557        double bestDistance)
 1163692558    {
 1163702559        if (bestDistance >= UnboundedDistanceCutoff || double.IsNaN(bestDistance)) return true;
 560
 1163682561        var tail = enumerator.TailLocation;
 1163682562        var head = enumerator.HeadLocation;
 1163682563        var minLon = tail.longitude < head.longitude ? tail.longitude : head.longitude;
 1163682564        var maxLon = tail.longitude > head.longitude ? tail.longitude : head.longitude;
 1163682565        var minLat = tail.latitude < head.latitude ? tail.latitude : head.latitude;
 1163682566        var maxLat = tail.latitude > head.latitude ? tail.latitude : head.latitude;
 567
 5905540568        foreach (var (sLon, sLat, _) in enumerator.Shape)
 1207247569        {
 1275120570            if (sLon < minLon) minLon = sLon;
 1199596571            else if (sLon > maxLon) maxLon = sLon;
 1272694572            if (sLat < minLat) minLat = sLat;
 1199819573            else if (sLat > maxLat) maxLat = sLat;
 1207247574        }
 575
 576        // Closest point on the bbox to the query, clamped per axis.
 1163682577        var cLon = center.longitude < minLon ? minLon
 1163682578            : center.longitude > maxLon ? maxLon : center.longitude;
 1163682579        var cLat = center.latitude < minLat ? minLat
 1163682580            : center.latitude > maxLat ? maxLat : center.latitude;
 1163682581        var closest = (cLon, cLat, (float?)null);
 1163682582        return closest.DistanceEstimateInMeter(center) <= bestDistance;
 1163692583    }
 584
 585    /// <summary>
 586    /// Tile-level predicate from snap-algorithm.md. Returns false if no edge
 587    /// with a vertex in this tile can possibly produce a snap within
 588    /// <paramref name="bestDistance"/> of the query, given the tile's own
 589    /// max edge extents.
 590    /// </summary>
 591    private static bool TileCanReach(
 592        (double minLon, double minLat, double maxLon, double maxLat) tileBbox,
 593        double tileMaxLonDiff,
 594        double tileMaxLatDiff,
 595        (double longitude, double latitude, float? e) center,
 596        double bestDistance)
 5393597    {
 5399598        if (bestDistance >= UnboundedDistanceCutoff || double.IsNaN(bestDistance)) return true;
 599
 5387600        var lonClosest = center.longitude < tileBbox.minLon ? tileBbox.minLon
 5387601            : center.longitude > tileBbox.maxLon ? tileBbox.maxLon : center.longitude;
 5387602        var latClosest = center.latitude < tileBbox.minLat ? tileBbox.minLat
 5387603            : center.latitude > tileBbox.maxLat ? tileBbox.maxLat : center.latitude;
 604
 5387605        var dLon = Math.Abs(center.longitude - lonClosest) - tileMaxLonDiff;
 10549606        if (dLon < 0) dLon = 0;
 5387607        var dLat = Math.Abs(center.latitude - latClosest) - tileMaxLatDiff;
 10575608        if (dLat < 0) dLat = 0;
 10394609        if (dLon == 0 && dLat == 0) return true;
 610
 611        // Convert the (dLon, dLat) offset at center.lat into meters by
 612        // measuring the haversine distance from center to a point offset by
 613        // exactly that much. Direction sign doesn't matter for distance.
 380614        var probe = (center.longitude + dLon, center.latitude + dLat, (float?)null);
 380615        return probe.DistanceEstimateInMeter(center) <= bestDistance;
 5393616    }
 617
 618    /// <summary>
 619    /// Per-vertex predicate from snap-algorithm.md. Same shape as
 620    /// <see cref="TileCanReach"/> but the "closest point of the tile bbox"
 621    /// becomes the vertex itself (the actual point, not a clamp).
 622    /// </summary>
 623    private static bool VertexCanReach(
 624        double vLon, double vLat,
 625        double tileMaxLonDiff,
 626        double tileMaxLatDiff,
 627        (double longitude, double latitude, float? e) center,
 628        double bestDistance)
 877093629    {
 877109630        if (bestDistance >= UnboundedDistanceCutoff || double.IsNaN(bestDistance)) return true;
 631
 877077632        var dLon = Math.Abs(center.longitude - vLon) - tileMaxLonDiff;
 1593478633        if (dLon < 0) dLon = 0;
 877077634        var dLat = Math.Abs(center.latitude - vLat) - tileMaxLatDiff;
 1697781635        if (dLat < 0) dLat = 0;
 1559078636        if (dLon == 0 && dLat == 0) return true;
 637
 195076638        var probe = (center.longitude + dLon, center.latitude + dLat, (float?)null);
 195076639        return probe.DistanceEstimateInMeter(center) <= bestDistance;
 877093640    }
 641
 642    /// <summary>
 643    /// Yields the tile coordinates on the perimeter of the square at
 644    /// <paramref name="ring"/> tiles around (<paramref name="cx"/>, <paramref name="cy"/>).
 645    /// Ring 0 is just the centre tile. Tile coords are unsigned, so the
 646    /// caller must filter against valid (in-box) bounds. We compute via
 647    /// <c>long</c> internally to handle the unsigned underflow safely when
 648    /// the centre tile is near (0, 0).
 649    /// </summary>
 650    private static IEnumerable<(uint x, uint y)> TilesInRing(uint cx, uint cy, uint ring)
 99651    {
 99652        if (ring == 0)
 96653        {
 96654            yield return (cx, cy);
 96655            yield break;
 656        }
 657
 3658        var startX = (long)cx - ring;
 3659        var endX = (long)cx + ring;
 3660        var startY = (long)cy - ring;
 3661        var endY = (long)cy + ring;
 662
 663        // Top row (y = startY), full width.
 3664        if (startY >= 0)
 3665        {
 24666            for (var x = startX; x <= endX; x++)
 18667                if (x >= 0) yield return ((uint)x, (uint)startY);
 3668        }
 669
 670        // Right column (x = endX), excluding the top-right corner already yielded.
 18671        for (var y = startY + 1; y <= endY; y++)
 12672            if (y >= 0) yield return ((uint)endX, (uint)y);
 673
 674        // Bottom row (y = endY), right-to-left, excluding the bottom-right corner.
 18675        for (var x = endX - 1; x >= startX; x--)
 12676            if (x >= 0) yield return ((uint)x, (uint)endY);
 677
 678        // Left column (x = startX), bottom-to-top, excluding both corners.
 3679        if (startX >= 0)
 3680        {
 12681            for (var y = endY - 1; y >= startY + 1; y--)
 6682                if (y >= 0) yield return ((uint)startX, (uint)y);
 3683        }
 3684    }
 685
 686    /// <summary>
 687    /// Distance between two unsigned tile indices, returning 0 if the second
 688    /// would underflow the first. Used to size the outermost ring needed to
 689    /// cover the search box without doing signed arithmetic on uints.
 690    /// </summary>
 384691    private static long SafeDelta(uint a, uint b) => a >= b ? (long)(a - b) : 0L;
 692
 693    /// <summary>
 694    /// Used only as a sort key: distance from the query to the tile bbox's
 695    /// closest point, ignoring the tile's max edge extents. Smaller = closer
 696    /// tile, processed first → bestDistance shrinks faster → more aggressive
 697    /// pruning on subsequent tiles.
 698    /// </summary>
 699    private static double ClosestBoxDistanceMeters(
 700        (double minLon, double minLat, double maxLon, double maxLat) bbox,
 701        (double longitude, double latitude, float? e) center)
 0702    {
 0703        var lonClosest = center.longitude < bbox.minLon ? bbox.minLon
 0704            : center.longitude > bbox.maxLon ? bbox.maxLon : center.longitude;
 0705        var latClosest = center.latitude < bbox.minLat ? bbox.minLat
 0706            : center.latitude > bbox.maxLat ? bbox.maxLat : center.latitude;
 0707        var probe = (lonClosest, latClosest, (float?)null);
 0708        return probe.DistanceEstimateInMeter(center);
 0709    }
 710}
Generated by: ReportGenerator 4.8.2.0
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

SnapInBoxAsync()
SnapAllInBoxAsync()
SnapToVertexInBoxAsync()
SnapToAllVerticesInBoxAsync()
SearchEdgesInBox(...)
EdgeBboxCanBeat(...)
TileCanReach(...)
VertexCanReach(...)
TilesInRing()
SafeDelta(...)
ClosestBoxDistanceMeters(...)