< Summary

Class:Itinero.Routing.Isochrones.IsochroneSearch
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Isochrones/IsochroneSearch.cs
Covered lines:201
Uncovered lines:4
Coverable lines:205
Total lines:314
Line coverage:98% (201 of 205)
Covered branches:74
Total branches:84
Branch coverage:88% (74 of 84)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
IsochroneAsync()78.57%1497.87%
<IsochroneAsync()83.33%676.92%
get_Cost()100%1100%
get_MinLon()100%1100%
get_SquareMetersPerSquareDegree()100%1100%
BuildSurface(...)100%20100%
Dilate(...)100%18100%
CellInDegrees(...)50%2100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Isochrones/IsochroneSearch.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;
 8using Itinero.Network.Enumerators.Edges;
 9using Itinero.Routing.Costs;
 10using Itinero.Routing.Flavours.Dijkstra;
 11using Itinero.Snapping;
 12
 13namespace Itinero.Routing.Isochrones;
 14
 15/// <summary>
 16/// Areas reachable from a point within given costs.
 17/// </summary>
 18/// <remarks>
 19/// One expansion, cut just past the outermost band, rasterised onto a grid and contoured. The
 20/// grid rather than a hull over reached vertices: edges carry shape, and a hull drawn between
 21/// endpoints would cut the corners off every long link.
 22/// </remarks>
 23public static class IsochroneSearch
 24{
 25    /// <summary>
 26    /// Computes the areas reachable from a snapped point at each of the given costs.
 27    /// </summary>
 28    /// <param name="bands">Cost bounds in the cost function's units. Order does not matter.</param>
 29    /// <returns>The bands, innermost first.</returns>
 30    public static async Task<Result<Isochrone>> IsochroneAsync(
 31        this RoutingNetwork network,
 32        RoutingSettings settings,
 33        SnapPoint source,
 34        IReadOnlyList<double> bands,
 35        IsochroneSettings? isochroneSettings = null,
 36        CancellationToken cancellationToken = default)
 1937    {
 2038        if (bands.Count == 0) throw new ArgumentException("No bands given.", nameof(bands));
 10339        foreach (var band in bands)
 2540        {
 2641            if (band <= 0) throw new ArgumentOutOfRangeException(nameof(bands),
 142                "A band has to cost more than nothing.");
 2443        }
 44
 1745        var options = isochroneSettings ?? new IsochroneSettings();
 1746        options.Validate();
 47
 2648        var ordered = bands.Distinct().OrderBy(x => x).ToList();
 1749        var outer = ordered[^1];
 50        // Searched past the outermost band so the contour has something on both sides of it to
 51        // interpolate between. Without it the boundary pulls in to the last reached vertex.
 1752        var cut = outer * (1.0 + options.Margin);
 53
 1754        var profile = settings.Profile;
 1755        var costFunction = network.GetCostFunctionFor(profile);
 1756        if (settings.CostFunctionWrapper != null) costFunction = settings.CostFunctionWrapper(costFunction);
 57
 1758        var reached = new Dictionary<VertexId, double>();
 1759        var settled = 0L;
 60
 1761        var search = SearchPool<Dijkstra>.Rent();
 62        try
 1763        {
 1764            await search.RunAsync(network, (source, (bool?)null),
 1765                [], costFunction.GetDijkstraWeightFunc(),
 1766                async state =>
 519167                {
 519168                    if (!network.UsageNotifier.IsVertexDataReady(network, state.vertexId))
 069                    {
 070                        await network.UsageNotifier.NotifyVertex(network, state.vertexId, cancellationToken);
 071                    }
 1772
 519173                    cancellationToken.ThrowIfCancellationRequested();
 519174                    settled++;
 1775
 1776                    // Cheapest arrival wins: the same vertex is settled once per incoming edge
 1777                    // in an edge-based search, and the surface wants the cost of being there.
 519178                    if (!reached.TryGetValue(state.vertexId, out var best) || state.cost < best)
 159379                    {
 159380                        reached[state.vertexId] = state.cost;
 159381                    }
 1782
 1783                    // True stops expansion from this state, which is what bounds the search.
 519184                    return state.cost > cut;
 519185                },
 1786                cancellationToken: cancellationToken,
 1787                isMainN: network.GetIsMainNFunc(profile));
 1788        }
 89        finally
 1790        {
 1791            SearchPool<Dijkstra>.Return(search);
 1792        }
 93
 1794        if (reached.Count == 0)
 095            return new Result<Isochrone>("Nothing reachable from the origin.");
 96
 1797        var grid = BuildSurface(network, reached, options, cancellationToken, out var diagnostics);
 1798        diagnostics = diagnostics with { Settled = settled, Reached = reached.Count };
 99
 17100        var result = new List<IsochroneBand>(ordered.Count);
 95101        foreach (var band in ordered)
 22102        {
 22103            result.Add(new IsochroneBand(band, ContourTracer.Trace(grid.Cost, grid.Width,
 22104                grid.Height, band, grid.MinLon, grid.MinLat, grid.LonPerCell, grid.LatPerCell,
 22105                options.Denoise, grid.SquareMetersPerSquareDegree,
 22106                options.FillHolesBelowSquareMeters, cancellationToken)));
 22107        }
 108
 17109        return new Isochrone(result, diagnostics);
 17110    }
 111
 112    private readonly record struct Surface(
 66113        double[] Cost, int Width, int Height,
 88114        double MinLon, double MinLat, double LonPerCell, double LatPerCell,
 22115        double SquareMetersPerSquareDegree);
 116
 117    /// <summary>
 118    /// Stamps the cost of every reached edge onto a grid, interpolating along the edge's shape.
 119    /// </summary>
 120    private static Surface BuildSurface(RoutingNetwork network,
 121        Dictionary<VertexId, double> reached, IsochroneSettings options,
 122        CancellationToken cancellationToken, out IsochroneDiagnostics diagnostics)
 17123    {
 17124        var minLon = double.MaxValue;
 17125        var minLat = double.MaxValue;
 17126        var maxLon = double.MinValue;
 17127        var maxLat = double.MinValue;
 3237128        foreach (var vertex in reached.Keys)
 1593129        {
 1593130            var (longitude, latitude, _) = network.GetVertex(vertex);
 1593131            minLon = Math.Min(minLon, longitude);
 1593132            minLat = Math.Min(minLat, latitude);
 1593133            maxLon = Math.Max(maxLon, longitude);
 1593134            maxLat = Math.Max(maxLat, latitude);
 1593135        }
 136
 17137        var centreLat = (minLat + maxLat) / 2.0;
 138
 139        // Scaled to the area actually reached when not given, so one setting serves a short walk
 140        // and an hour's drive. Valhalla sizes its grid the same way.
 17141        var cellSize = options.CellSizeMeters ?? 0;
 17142        if (cellSize <= 0)
 3143        {
 3144            var southWest = (minLon, minLat, (float?)null);
 3145            var across = Math.Max(
 3146                southWest.DistanceEstimateInMeter((maxLon, minLat, (float?)null)),
 3147                southWest.DistanceEstimateInMeter((minLon, maxLat, (float?)null)));
 3148            cellSize = Math.Max(options.MinCellSizeMeters, across / options.TargetCellsAcross);
 3149        }
 150
 17151        var (lonPerCell, latPerCell) = CellInDegrees(cellSize, centreLat);
 152
 17153        var width = (int)Math.Ceiling((maxLon - minLon) / lonPerCell) + 1;
 17154        var height = (int)Math.Ceiling((maxLat - minLat) / latPerCell) + 1;
 155
 156        // Coarsen rather than allocate without bound: a wide band over a sparse network would
 157        // otherwise size the grid off its own extent.
 17158        if ((long)width * height > options.MaxCells)
 1159        {
 1160            var factor = Math.Sqrt((double)width * height / options.MaxCells);
 1161            cellSize *= factor;
 1162            (lonPerCell, latPerCell) = CellInDegrees(cellSize, centreLat);
 1163            width = (int)Math.Ceiling((maxLon - minLon) / lonPerCell) + 1;
 1164            height = (int)Math.Ceiling((maxLat - minLat) / latPerCell) + 1;
 1165        }
 166
 167        // Padded by the reach, so a dilated band never runs into the edge of the grid and
 168        // leaves a ring that cannot close.
 17169        var pad = (int)Math.Round(options.ReachRadiusMeters / cellSize) + 2;
 17170        width += pad * 2;
 17171        height += pad * 2;
 17172        minLon -= lonPerCell * pad;
 17173        minLat -= latPerCell * pad;
 174
 17175        var cost = new double[(long)width * height];
 17176        Array.Fill(cost, double.MaxValue);
 177
 17178        var enumerator = network.GetEdgeEnumerator();
 17179        var seen = new HashSet<EdgeId>();
 17180        var stamped = 0;
 3237181        foreach (var vertex in reached.Keys)
 1593182        {
 183            // One pass per reached vertex, each walking every incident edge's shape.
 1610184            if ((stamped++ & 0xFF) == 0) cancellationToken.ThrowIfCancellationRequested();
 1593185            if (!enumerator.MoveTo(vertex)) continue;
 7559186            while (enumerator.MoveNext())
 5966187            {
 8798188                if (!seen.Add(enumerator.EdgeId)) continue;
 3134189                if (!reached.TryGetValue(enumerator.Tail, out var tailCost)) continue;
 3436190                if (!reached.TryGetValue(enumerator.Head, out var headCost)) continue;
 191
 2832192                Stamp(enumerator, tailCost, headCost);
 2832193            }
 1593194        }
 195
 17196        Dilate(cost, width, height, (int)Math.Round(options.ReachRadiusMeters / cellSize),
 17197            cancellationToken);
 198
 17199        diagnostics = new IsochroneDiagnostics(0, 0, (long)width * height, cellSize);
 200        // One square degree in square metres here, so a hole's area can be judged in metres.
 17201        var metersPerDegreeLon = cellSize / lonPerCell;
 17202        var metersPerDegreeLat = cellSize / latPerCell;
 17203        return new Surface(cost, width, height, minLon, minLat, lonPerCell, latPerCell,
 17204            metersPerDegreeLon * metersPerDegreeLat);
 205
 206        void Stamp(RoutingNetworkEdgeEnumerator edge, double tailCost, double headCost)
 2832207        {
 2832208            var shape = edge.GetCompleteShape().ToList();
 2832209            if (shape.Count < 2) return;
 210
 2832211            var lengths = new double[shape.Count];
 2832212            var total = 0d;
 11328213            for (var i = 1; i < shape.Count; i++)
 2832214            {
 2832215                total += shape[i - 1].DistanceEstimateInMeter(shape[i]);
 2832216                lengths[i] = total;
 2832217            }
 218
 16992219            for (var i = 0; i < shape.Count; i++)
 5664220            {
 5664221                var at = total <= 0 ? 0 : lengths[i] / total;
 5664222                var here = tailCost + (headCost - tailCost) * at;
 5664223                Mark(shape[i].longitude, shape[i].latitude, here);
 224
 8496225                if (i + 1 >= shape.Count) continue;
 226
 227                // Sample between shape points too: a cell the edge merely crosses must be
 228                // marked, or a straight link longer than a cell leaves gaps in the surface.
 2832229                var span = lengths[i + 1] - lengths[i];
 2832230                var steps = (int)Math.Floor(span / cellSize);
 20842231                for (var s = 1; s <= steps; s++)
 7589232                {
 7589233                    var f = s / (double)(steps + 1);
 7589234                    var lon = shape[i].longitude + (shape[i + 1].longitude - shape[i].longitude) * f;
 7589235                    var lat = shape[i].latitude + (shape[i + 1].latitude - shape[i].latitude) * f;
 7589236                    var mid = total <= 0
 7589237                        ? here
 7589238                        : tailCost + (headCost - tailCost) * ((lengths[i] + span * f) / total);
 7589239                    Mark(lon, lat, mid);
 7589240                }
 2832241            }
 2832242        }
 243
 244        void Mark(double longitude, double latitude, double value)
 13253245        {
 13253246            var x = (int)Math.Round((longitude - minLon) / lonPerCell);
 13253247            var y = (int)Math.Round((latitude - minLat) / latPerCell);
 13253248            if (x < 0 || y < 0 || x >= width || y >= height) return;
 249
 13253250            var index = (long)y * width + x;
 20706251            if (value < cost[index]) cost[index] = value;
 13253252        }
 17253    }
 254
 255    /// <summary>
 256    /// Spreads each cell's cost to those within <paramref name="radius"/> cells of it.
 257    /// </summary>
 258    /// <remarks>
 259    /// Separable: the minimum over a square is the minimum along each row, then down each
 260    /// column. Taking the minimum is what makes it mean "the cheapest road within reach".
 261    /// </remarks>
 262    private static void Dilate(double[] cost, int width, int height, int radius,
 263        CancellationToken cancellationToken = default)
 17264    {
 19265        if (radius < 1) return;
 266
 15267        var row = new double[width];
 1514268        for (var y = 0; y < height; y++)
 742269        {
 270            // Per row rather than per cell: the grid runs to millions of cells.
 742271            cancellationToken.ThrowIfCancellationRequested();
 742272            var offset = (long)y * width;
 92534273            for (var x = 0; x < width; x++) row[x] = cost[offset + x];
 62184274            for (var x = 0; x < width; x++)
 30350275            {
 30350276                var best = double.MaxValue;
 30350277                var from = Math.Max(0, x - radius);
 30350278                var to = Math.Min(width - 1, x + radius);
 1152910279                for (var i = from; i <= to; i++) best = Math.Min(best, row[i]);
 30350280                cost[offset + x] = best;
 30350281            }
 742282        }
 283
 15284        var column = new double[height];
 1182285        for (var x = 0; x < width; x++)
 576286        {
 576287            cancellationToken.ThrowIfCancellationRequested();
 92202288            for (var y = 0; y < height; y++) column[y] = cost[(long)y * width + x];
 61852289            for (var y = 0; y < height; y++)
 30350290            {
 30350291                var best = double.MaxValue;
 30350292                var from = Math.Max(0, y - radius);
 30350293                var to = Math.Min(height - 1, y + radius);
 1172986294                for (var i = from; i <= to; i++) best = Math.Min(best, column[i]);
 30350295                cost[(long)y * width + x] = best;
 30350296            }
 576297        }
 17298    }
 299
 300    /// <summary>
 301    /// Cell size in degrees. Taken once at the centre latitude rather than per point: the
 302    /// longitude scale varies across a band, but not enough to matter at a cell's size.
 303    /// </summary>
 304    private static (double lonPerCell, double latPerCell) CellInDegrees(double meters, double latitude)
 18305    {
 306        const double metersPerDegreeLat = 111_320.0;
 18307        var latPerCell = meters / metersPerDegreeLat;
 18308        var cos = Math.Cos(latitude * Math.PI / 180.0);
 18309        var lonPerCell = Math.Abs(cos) < 1e-6
 18310            ? latPerCell
 18311            : meters / (metersPerDegreeLat * cos);
 18312        return (lonPerCell, latPerCell);
 18313    }
 314}