< 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:185
Uncovered lines:47
Coverable lines:232
Total lines:405
Line coverage:79.7% (185 of 232)
Covered branches:86
Total branches:118
Branch coverage:72.8% (86 of 118)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
SnapInBoxAsync()90%5094.11%
SnapAllInBoxAsync()93.18%44100%
SnapToVertexInBoxAsync()0%120%
SnapToAllVerticesInBoxAsync()0%120%
SearchEdgesInBox(...)100%1100%

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.Snapping;
 9
 10namespace Itinero.Network.Search.Edges;
 11
 12internal static class EdgeSearch
 13{
 14    /// <summary>
 15    /// Returns the closest edge to the center of the given box that has at least one vertex inside the given box.
 16    /// </summary>
 17    /// <param name="network">The network.</param>
 18    /// <param name="searchBox">The box to search in.</param>
 19    /// <param name="maxDistance">The maximum distance of any snap point returned relative to the center of the search b
 20    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 21    /// <param name="cancellationToken">The cancellation token.</param>
 22    /// <returns>The closest edge to the center of the box inside the given box.</returns>
 23    public static async Task<SnapPoint> SnapInBoxAsync(this RoutingNetwork network,
 24        ((double longitude, double, float? e) topLeft, (double longitude, double latitude, float? e) bottomRight)
 25            searchBox,
 26        IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, CancellationToken cancellationToken = de
 5927    {
 5928        var edgeEnumerator = network.SearchEdgesInBox(searchBox);
 5929        var center = searchBox.Center();
 30
 31        const double exactTolerance = 1;
 5932        var bestDistance = maxDistance;
 5933        (EdgeId edgeId, ushort offset) bestSnapPoint = (EdgeId.Empty, ushort.MaxValue);
 13834        while (edgeEnumerator.MoveNext())
 11535        {
 15136            if (bestDistance <= 0) break; // break when exact on an edge.
 37
 38            // search for the local snap point that improves the current best snap point.
 7939            (EdgeId edgeId, double offset) localSnapPoint = (EdgeId.Empty, 0);
 7940            var isAcceptable = edgeChecker == null ? (bool?)true : null;
 7941            var completeShape = edgeEnumerator.GetCompleteShape();
 7942            var length = 0.0;
 7943            using (var completeShapeEnumerator = completeShape.GetEnumerator())
 7944            {
 7945                completeShapeEnumerator.MoveNext();
 7946                var previous = completeShapeEnumerator.Current;
 47
 48                // start with the first location.
 7949                var distance = previous.DistanceEstimateInMeter(center);
 7950                if (distance < bestDistance)
 4951                {
 4952                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 4953                                                              await edgeChecker.RunCheckAsync(edgeEnumerator, cancellati
 4954                    if (!isAcceptable.Value)
 055                    {
 056                        continue;
 57                    }
 58
 4959                    if (distance < exactTolerance)
 3560                    {
 3561                        distance = 0;
 3562                    }
 63
 4964                    bestDistance = distance;
 4965                    localSnapPoint = (edgeEnumerator.EdgeId, 0);
 4966                }
 67
 68                // loop over all pairs.
 19069                while (completeShapeEnumerator.MoveNext())
 11170                {
 11171                    var current = completeShapeEnumerator.Current;
 72
 11173                    var segmentLength = previous.DistanceEstimateInMeter(current);
 74
 75                    // first check the actual current location, it may be an exact match.
 11176                    distance = current.DistanceEstimateInMeter(center);
 11177                    if (distance < bestDistance)
 3578                    {
 3579                        isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 3580                                         await edgeChecker.RunCheckAsync(edgeEnumerator, cancellationToken);
 3581                        if (!isAcceptable.Value)
 082                        {
 083                            break;
 84                        }
 85
 3586                        if (distance < exactTolerance)
 1887                        {
 1888                            distance = 0;
 1889                        }
 90
 3591                        bestDistance = distance;
 3592                        localSnapPoint = (edgeEnumerator.EdgeId, length + segmentLength);
 3593                    }
 94
 95                    // update length.
 11196                    var startLength = length;
 11197                    length += segmentLength;
 98
 99                    // TODO: figure this out, there has to be a way to not project every segment.
 100                    //                        // check if we even need to check.
 101                    //                        var previousDistance = previous.DistanceEstimateInMeter(center);
 102                    //                        var shapePointDistance = current.DistanceEstimateInMeter(center);
 103                    //                        if (previousDistance + segmentLength > bestDistance &&
 104                    //                            shapePointDistance + segmentLength > bestDistance)
 105                    //                        {
 106                    //                            continue;
 107                    //                        }
 108
 109                    // project on line segment.
 111110                    var line = (previous, current);
 111111                    var originalPrevious = previous;
 111112                    previous = current;
 111113                    if (bestDistance <= 0)
 68114                    {
 115                        // we need to continue, we need the total length.
 68116                        continue;
 117                    }
 118
 43119                    var projected = line.ProjectOn(center);
 43120                    if (!projected.HasValue)
 24121                    {
 24122                        continue;
 123                    }
 124
 19125                    distance = projected.Value.DistanceEstimateInMeter(center);
 19126                    if (!(distance < bestDistance))
 5127                    {
 5128                        continue;
 129                    }
 130
 14131                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 14132                                     await edgeChecker.RunCheckAsync(edgeEnumerator, cancellationToken);
 14133                    if (!isAcceptable.Value)
 0134                    {
 0135                        break;
 136                    }
 137
 14138                    if (distance < exactTolerance)
 3139                    {
 3140                        distance = 0;
 3141                    }
 142
 14143                    bestDistance = distance;
 14144                    localSnapPoint = (edgeEnumerator.EdgeId,
 14145                        startLength + originalPrevious.DistanceEstimateInMeter(projected.Value));
 14146                }
 79147            }
 148
 149            // move to the nex edge if no better point was found.
 79150            if (localSnapPoint.edgeId == EdgeId.Empty)
 9151            {
 9152                continue;
 153            }
 154
 155            // calculate the actual offset.
 70156            var offset = ushort.MaxValue;
 70157            if (localSnapPoint.offset < length)
 52158            {
 52159                if (localSnapPoint.offset <= 0)
 40160                {
 40161                    offset = 0;
 40162                }
 163                else
 12164                {
 12165                    offset = (ushort)(localSnapPoint.offset / length * ushort.MaxValue);
 12166                }
 52167            }
 168
 169            // invert offset if edge is reversed.
 70170            if (!edgeEnumerator.Forward)
 16171            {
 16172                offset = (ushort)(ushort.MaxValue - offset);
 16173            }
 174
 70175            bestSnapPoint = (localSnapPoint.edgeId, offset);
 70176        }
 177
 59178        return new SnapPoint(bestSnapPoint.edgeId, bestSnapPoint.offset);
 59179    }
 180
 181    /// <summary>
 182    /// Snaps all points in the given box that could potentially be snapping points.
 183    /// </summary>
 184    /// <param name="routerDb"></param>
 185    /// <param name="searchBox">The box to search in.</param>
 186    /// <param name="maxDistance">The maximum distance of any snap point returned relative to the center of the search b
 187    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 188    /// <param name="nonOrthogonalEdges">When true the best potential location on each edge is returned, when false only
 189    /// <param name="cancellationToken">The cancellation token.</param>
 190    /// <returns>All edges that could potentially be relevant snapping points, not only the closest.</returns>
 191    public static async IAsyncEnumerable<SnapPoint> SnapAllInBoxAsync(this RoutingNetwork routerDb,
 192        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 193            bottomRight) searchBox,
 194        IEdgeChecker? edgeChecker = null, bool nonOrthogonalEdges = true, double maxDistance = double.MaxValue, Cancella
 2109195    {
 2109196        var edges = new HashSet<EdgeId>();
 197
 2109198        var edgeEnumerator = routerDb.SearchEdgesInBox(searchBox);
 2109199        var center = searchBox.Center();
 200
 2462279201        while (edgeEnumerator.MoveNext())
 2460170202        {
 3646612203            if (!edges.Add(edgeEnumerator.EdgeId)) continue;
 204
 205            // search for the best snap point for the current edge.
 1273728206            (EdgeId edgeId, double offset, bool isOrthoganal, double distance) bestEdgeSnapPoint =
 1273728207                (EdgeId.Empty, 0, false, maxDistance);
 1273728208            var isAcceptable = edgeChecker == null ? (bool?)true : null;
 1273728209            var completeShape = edgeEnumerator.GetCompleteShape();
 1273728210            var length = 0.0;
 1273728211            using (var completeShapeEnumerator = completeShape.GetEnumerator())
 1273728212            {
 1273728213                completeShapeEnumerator.MoveNext();
 1273728214                var previous = completeShapeEnumerator.Current;
 215
 216                // start with the first location.
 1273728217                var distance = previous.DistanceEstimateInMeter(center);
 1273728218                if (distance < bestEdgeSnapPoint.distance)
 48096219                {
 48096220                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync(edgeEn
 48096221                    if (!isAcceptable.Value)
 22702222                    {
 22702223                        continue;
 224                    }
 225
 25394226                    bestEdgeSnapPoint = (edgeEnumerator.EdgeId, 0, false, distance);
 25394227                }
 228
 229                // loop over all pairs.
 3766889230                while (completeShapeEnumerator.MoveNext())
 2519074231                {
 2519074232                    var current = completeShapeEnumerator.Current;
 233
 2519074234                    var segmentLength = previous.DistanceEstimateInMeter(current);
 235
 236                    // first check the actual current location, it may be an exact match.
 2519074237                    distance = current.DistanceEstimateInMeter(center);
 2519074238                    if (distance < bestEdgeSnapPoint.distance)
 32109239                    {
 32109240                        isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync(ed
 32109241                        if (!isAcceptable.Value)
 3211242                        {
 3211243                            break;
 244                        }
 245
 28898246                        bestEdgeSnapPoint = (edgeEnumerator.EdgeId, length + segmentLength, false, distance);
 28898247                    }
 248
 249                    // update length.
 2515863250                    var startLength = length;
 2515863251                    length += segmentLength;
 252
 253                    // project on line segment.
 2515863254                    var line = (previous, current);
 2515863255                    var originalPrevious = previous;
 2515863256                    previous = current;
 257
 2515863258                    var projected = line.ProjectOn(center);
 2515863259                    if (projected.HasValue)
 17109260                    {
 17109261                        distance = projected.Value.DistanceEstimateInMeter(center);
 17109262                        if (distance < bestEdgeSnapPoint.distance)
 4508263                        {
 4508264                            isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsyn
 4508265                            if (isAcceptable.Value)
 4482266                            {
 4482267                                bestEdgeSnapPoint = (edgeEnumerator.EdgeId,
 4482268                                    startLength + originalPrevious.DistanceEstimateInMeter(projected.Value),
 4482269                                    true, distance);
 4482270                            }
 4508271                        }
 17109272                    }
 2515863273                }
 1251026274            }
 275
 276            // move to the nex edge if no snap point was found.
 1251026277            if (bestEdgeSnapPoint.edgeId == EdgeId.Empty)
 1219392278            {
 1219392279                continue;
 280            }
 281
 282            // check type and return if needed.
 31634283            var returnEdge = bestEdgeSnapPoint.isOrthoganal || nonOrthogonalEdges;
 31634284            if (!returnEdge)
 1285            {
 1286                continue;
 287            }
 288
 289            // calculate the actual offset.
 31633290            var offset = ushort.MaxValue;
 31633291            if (bestEdgeSnapPoint.offset < length)
 18903292            {
 18903293                if (bestEdgeSnapPoint.offset <= 0)
 13080294                {
 13080295                    offset = 0;
 13080296                }
 297                else
 5823298                {
 5823299                    offset = (ushort)(bestEdgeSnapPoint.offset / length * ushort.MaxValue);
 5823300                }
 18903301            }
 302
 303            // invert offset if edge is reversed.
 31633304            if (!edgeEnumerator.Forward)
 9628305            {
 9628306                offset = (ushort)(ushort.MaxValue - offset);
 9628307            }
 308
 31633309            yield return new SnapPoint(bestEdgeSnapPoint.edgeId, offset);
 31633310        }
 2109311    }
 312
 313    /// <summary>
 314    /// Returns the closest vertex to the center of the given box.
 315    /// </summary>
 316    /// <param name="network">The network.</param>
 317    /// <param name="searchBox">The box to search in.</param>
 318    /// <param name="maxDistance">The maximum distance of any vertex returned relative to the center of the search box.<
 319    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 320    /// <param name="cancellationToken">The cancellation token.</param>
 321    /// <returns>The closest edge to the center of the box inside the given box.</returns>
 322    public static async Task<VertexId> SnapToVertexInBoxAsync(this RoutingNetwork network,
 323        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 324            bottomRight) searchBox, IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, Cancellation
 0325    {
 0326        var center = searchBox.Center();
 0327        var closestDistance = maxDistance;
 0328        var closest = VertexId.Empty;
 329
 0330        var vertices = network.SearchVerticesInBox(searchBox);
 0331        var edgeEnumerator = network.GetEdgeEnumerator();
 0332        foreach (var (vertex, location) in vertices)
 0333        {
 0334            var d = center.DistanceEstimateInMeter(location);
 0335            if (d > closestDistance) continue;
 336
 0337            if (edgeChecker == null)
 0338            {
 0339                closest = vertex;
 0340                closestDistance = d;
 0341                continue;
 342            }
 343
 0344            edgeEnumerator.MoveTo(vertex);
 0345            while (edgeEnumerator.MoveNext())
 0346            {
 0347                if (!(edgeChecker.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync(edgeEnumerator, cancel
 348
 0349                closest = vertex;
 0350                closestDistance = d;
 0351                break;
 352            }
 0353        }
 354
 0355        return closest;
 0356    }
 357
 358    /// <summary>
 359    /// Snaps all vertices in the given box that could potentially be snapping vertices.
 360    /// </summary>
 361    /// <param name="network">The network.</param>
 362    /// <param name="searchBox">The box to search in.</param>
 363    /// <param name="maxDistance">The maximum distance of any vertex returned relative to the center of the search box.<
 364    /// <param name="edgeChecker">Used to determine if an edge is acceptable or not. If null any edge will be accepted.<
 365    /// <param name="cancellationToken">The cancellation token.</param>
 366    /// <returns>All the vertices within the box with at least one acceptable edge.</returns>
 367    public static async IAsyncEnumerable<VertexId> SnapToAllVerticesInBoxAsync(this RoutingNetwork network,
 368        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 369            bottomRight) searchBox,
 370        IEdgeChecker? edgeChecker = null, double maxDistance = double.MaxValue, CancellationToken cancellationToken = de
 0371    {
 0372        var center = searchBox.Center();
 0373        var vertices = network.SearchVerticesInBox(searchBox);
 0374        var edgeEnumerator = network.GetEdgeEnumerator();
 0375        foreach (var (vertex, location) in vertices)
 0376        {
 0377            edgeEnumerator.MoveTo(vertex);
 378
 0379            var d = center.DistanceEstimateInMeter(location);
 0380            if (d > maxDistance) continue;
 381
 0382            while (edgeEnumerator.MoveNext())
 0383            {
 0384                if (edgeChecker != null && !(edgeChecker.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync
 385
 0386                yield return vertex;
 0387                break;
 388            }
 0389        }
 0390    }
 391
 392    /// <summary>
 393    /// Enumerates all edges that have at least one vertex in the given bounding box.
 394    /// </summary>
 395    /// <param name="network">The network.</param>
 396    /// <param name="box">The box to enumerate in.</param>
 397    /// <returns>An enumerator with all the vertices and their location.</returns>
 398    public static IEdgeEnumerator<RoutingNetwork> SearchEdgesInBox(this RoutingNetwork network,
 399        ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 400            bottomRight) box)
 2170401    {
 2170402        var vertices = network.SearchVerticesInBox(box);
 886309403        return new VertexEdgeEnumerator(network, vertices.Select((i) => i.vertex));
 2170404    }
 405}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

SnapInBoxAsync()
SnapAllInBoxAsync()
SnapToVertexInBoxAsync()
SnapToAllVerticesInBoxAsync()
SearchEdgesInBox(...)