< 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:172
Uncovered lines:60
Coverable lines:232
Total lines:405
Line coverage:74.1% (172 of 232)
Covered branches:70
Total branches:118
Branch coverage:59.3% (70 of 118)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
SnapInBoxAsync()80%5090.19%
SnapAllInBoxAsync()68.18%4489.41%
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
 2527    {
 2528        var edgeEnumerator = network.SearchEdgesInBox(searchBox);
 2529        var center = searchBox.Center();
 30
 31        const double exactTolerance = 1;
 2532        var bestDistance = maxDistance;
 2533        (EdgeId edgeId, ushort offset) bestSnapPoint = (EdgeId.Empty, ushort.MaxValue);
 5534        while (edgeEnumerator.MoveNext())
 5035        {
 7036            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.
 3039            (EdgeId edgeId, double offset) localSnapPoint = (EdgeId.Empty, 0);
 3040            var isAcceptable = edgeChecker == null ? (bool?)true : null;
 3041            var completeShape = edgeEnumerator.GetCompleteShape();
 3042            var length = 0.0;
 3043            using (var completeShapeEnumerator = completeShape.GetEnumerator())
 3044            {
 3045                completeShapeEnumerator.MoveNext();
 3046                var previous = completeShapeEnumerator.Current;
 47
 48                // start with the first location.
 3049                var distance = previous.DistanceEstimateInMeter(center);
 3050                if (distance < bestDistance)
 1751                {
 1752                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 1753                                                              await edgeChecker.RunCheckAsync(edgeEnumerator, cancellati
 1754                    if (!isAcceptable.Value)
 055                    {
 056                        continue;
 57                    }
 58
 1759                    if (distance < exactTolerance)
 1260                    {
 1261                        distance = 0;
 1262                    }
 63
 1764                    bestDistance = distance;
 1765                    localSnapPoint = (edgeEnumerator.EdgeId, 0);
 1766                }
 67
 68                // loop over all pairs.
 9269                while (completeShapeEnumerator.MoveNext())
 6270                {
 6271                    var current = completeShapeEnumerator.Current;
 72
 6273                    var segmentLength = previous.DistanceEstimateInMeter(current);
 74
 75                    // first check the actual current location, it may be an exact match.
 6276                    distance = current.DistanceEstimateInMeter(center);
 6277                    if (distance < bestDistance)
 2678                    {
 2679                        isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 2680                                         await edgeChecker.RunCheckAsync(edgeEnumerator, cancellationToken);
 2681                        if (!isAcceptable.Value)
 082                        {
 083                            break;
 84                        }
 85
 2686                        if (distance < exactTolerance)
 987                        {
 988                            distance = 0;
 989                        }
 90
 2691                        bestDistance = distance;
 2692                        localSnapPoint = (edgeEnumerator.EdgeId, length + segmentLength);
 2693                    }
 94
 95                    // update length.
 6296                    var startLength = length;
 6297                    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.
 62110                    var line = (previous, current);
 62111                    var originalPrevious = previous;
 62112                    previous = current;
 62113                    if (bestDistance <= 0)
 36114                    {
 115                        // we need to continue, we need the total length.
 36116                        continue;
 117                    }
 118
 26119                    var projected = line.ProjectOn(center);
 26120                    if (!projected.HasValue)
 17121                    {
 17122                        continue;
 123                    }
 124
 9125                    distance = projected.Value.DistanceEstimateInMeter(center);
 9126                    if (!(distance < bestDistance))
 0127                    {
 0128                        continue;
 129                    }
 130
 9131                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ??
 9132                                     await edgeChecker.RunCheckAsync(edgeEnumerator, cancellationToken);
 9133                    if (!isAcceptable.Value)
 0134                    {
 0135                        break;
 136                    }
 137
 9138                    if (distance < exactTolerance)
 3139                    {
 3140                        distance = 0;
 3141                    }
 142
 9143                    bestDistance = distance;
 9144                    localSnapPoint = (edgeEnumerator.EdgeId,
 9145                        startLength + originalPrevious.DistanceEstimateInMeter(projected.Value));
 9146                }
 30147            }
 148
 149            // move to the nex edge if no better point was found.
 30150            if (localSnapPoint.edgeId == EdgeId.Empty)
 0151            {
 0152                continue;
 153            }
 154
 155            // calculate the actual offset.
 30156            var offset = ushort.MaxValue;
 30157            if (localSnapPoint.offset < length)
 21158            {
 21159                if (localSnapPoint.offset <= 0)
 14160                {
 14161                    offset = 0;
 14162                }
 163                else
 7164                {
 7165                    offset = (ushort)(localSnapPoint.offset / length * ushort.MaxValue);
 7166                }
 21167            }
 168
 169            // invert offset if edge is reversed.
 30170            if (!edgeEnumerator.Forward)
 4171            {
 4172                offset = (ushort)(ushort.MaxValue - offset);
 4173            }
 174
 30175            bestSnapPoint = (localSnapPoint.edgeId, offset);
 30176        }
 177
 25178        return new SnapPoint(bestSnapPoint.edgeId, bestSnapPoint.offset);
 25179    }
 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
 2195    {
 2196        var edges = new HashSet<EdgeId>();
 197
 2198        var edgeEnumerator = routerDb.SearchEdgesInBox(searchBox);
 2199        var center = searchBox.Center();
 200
 14201        while (edgeEnumerator.MoveNext())
 12202        {
 18203            if (!edges.Add(edgeEnumerator.EdgeId)) continue;
 204
 205            // search for the best snap point for the current edge.
 6206            (EdgeId edgeId, double offset, bool isOrthoganal, double distance) bestEdgeSnapPoint =
 6207                (EdgeId.Empty, 0, false, maxDistance);
 6208            var isAcceptable = edgeChecker == null ? (bool?)true : null;
 6209            var completeShape = edgeEnumerator.GetCompleteShape();
 6210            var length = 0.0;
 6211            using (var completeShapeEnumerator = completeShape.GetEnumerator())
 6212            {
 6213                completeShapeEnumerator.MoveNext();
 6214                var previous = completeShapeEnumerator.Current;
 215
 216                // start with the first location.
 6217                var distance = previous.DistanceEstimateInMeter(center);
 6218                if (distance < bestEdgeSnapPoint.distance)
 6219                {
 6220                    isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync(edgeEn
 6221                    if (!isAcceptable.Value)
 0222                    {
 0223                        continue;
 224                    }
 225
 6226                    bestEdgeSnapPoint = (edgeEnumerator.EdgeId, 0, false, distance);
 6227                }
 228
 229                // loop over all pairs.
 12230                while (completeShapeEnumerator.MoveNext())
 6231                {
 6232                    var current = completeShapeEnumerator.Current;
 233
 6234                    var segmentLength = previous.DistanceEstimateInMeter(current);
 235
 236                    // first check the actual current location, it may be an exact match.
 6237                    distance = current.DistanceEstimateInMeter(center);
 6238                    if (distance < bestEdgeSnapPoint.distance)
 4239                    {
 4240                        isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsync(ed
 4241                        if (!isAcceptable.Value)
 0242                        {
 0243                            break;
 244                        }
 245
 4246                        bestEdgeSnapPoint = (edgeEnumerator.EdgeId, length + segmentLength, false, distance);
 4247                    }
 248
 249                    // update length.
 6250                    var startLength = length;
 6251                    length += segmentLength;
 252
 253                    // project on line segment.
 6254                    var line = (previous, current);
 6255                    var originalPrevious = previous;
 6256                    previous = current;
 257
 6258                    var projected = line.ProjectOn(center);
 6259                    if (projected.HasValue)
 4260                    {
 4261                        distance = projected.Value.DistanceEstimateInMeter(center);
 4262                        if (distance < bestEdgeSnapPoint.distance)
 4263                        {
 4264                            isAcceptable ??= edgeChecker!.IsAcceptable(edgeEnumerator) ?? await edgeChecker.RunCheckAsyn
 4265                            if (isAcceptable.Value)
 4266                            {
 4267                                bestEdgeSnapPoint = (edgeEnumerator.EdgeId,
 4268                                    startLength + originalPrevious.DistanceEstimateInMeter(projected.Value),
 4269                                    true, distance);
 4270                            }
 4271                        }
 4272                    }
 6273                }
 6274            }
 275
 276            // move to the nex edge if no snap point was found.
 6277            if (bestEdgeSnapPoint.edgeId == EdgeId.Empty)
 0278            {
 0279                continue;
 280            }
 281
 282            // check type and return if needed.
 6283            var returnEdge = bestEdgeSnapPoint.isOrthoganal || nonOrthogonalEdges;
 6284            if (!returnEdge)
 1285            {
 1286                continue;
 287            }
 288
 289            // calculate the actual offset.
 5290            var offset = ushort.MaxValue;
 5291            if (bestEdgeSnapPoint.offset < length)
 5292            {
 5293                if (bestEdgeSnapPoint.offset <= 0)
 1294                {
 1295                    offset = 0;
 1296                }
 297                else
 4298                {
 4299                    offset = (ushort)(bestEdgeSnapPoint.offset / length * ushort.MaxValue);
 4300                }
 5301            }
 302
 303            // invert offset if edge is reversed.
 5304            if (!edgeEnumerator.Forward)
 0305            {
 0306                offset = (ushort)(ushort.MaxValue - offset);
 0307            }
 308
 5309            yield return new SnapPoint(bestEdgeSnapPoint.edgeId, offset);
 5310        }
 2311    }
 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)
 29401    {
 29402        var vertices = network.SearchVerticesInBox(box);
 91403        return new VertexEdgeEnumerator(network, vertices.Select((i) => i.vertex));
 29404    }
 405}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

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