< Summary

Class:Itinero.Routing.Isochrones.ContourTracer
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Isochrones/ContourTracer.cs
Covered lines:158
Uncovered lines:2
Coverable lines:160
Total lines:269
Line coverage:98.7% (158 of 160)
Covered branches:106
Total branches:117
Branch coverage:90.5% (106 of 117)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
Trace(...)100%35100%
Fraction(...)66.66%12100%
Assemble(...)87.5%4896.29%
SignedArea(...)100%2100%
Contains(...)100%6100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Isochrones/ContourTracer.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Threading;
 4
 5namespace Itinero.Routing.Isochrones;
 6
 7/// <summary>
 8/// Marching squares over a cost grid: turns "cost at each grid corner" into closed rings at a
 9/// given cost.
 10/// </summary>
 11/// <remarks>
 12/// Segments are emitted with the reachable side on the left, so an outer boundary comes out
 13/// counter-clockwise and a hole clockwise — which is both how they are told apart here and the
 14/// winding GeoJSON asks for.
 15/// </remarks>
 16internal static class ContourTracer
 17{
 18    // Which cell side a crossing sits on. Used to give every crossing an exact integer identity,
 19    // so segments are joined by lattice position rather than by comparing interpolated doubles.
 20    private const int Bottom = 0;
 21    private const int Right = 1;
 22    private const int Top = 2;
 23    private const int Left = 3;
 24
 25    /// <summary>
 26    /// Traces the band at <paramref name="band"/> out of a corner-cost grid.
 27    /// </summary>
 28    /// <param name="cost">Cost per corner, row-major, <see cref="double.MaxValue"/> if unreached.</param>
 29    /// <param name="width">Corners per row.</param>
 30    /// <param name="height">Rows of corners.</param>
 31    public static List<IsochronePolygon> Trace(double[] cost, int width, int height, double band,
 32        double minLon, double minLat, double lonPerCell, double latPerCell, double denoise,
 33        double squareMetersPerSquareDegree = 0, double fillHolesBelow = 0,
 34        CancellationToken cancellationToken = default)
 2435    {
 2436        var segments = new List<(long from, long to)>();
 2437        var points = new Dictionary<long, (double longitude, double latitude)>();
 38
 228239        for (var y = 0; y < height - 1; y++)
 111840        {
 41            // Per row: a band over a wide area is millions of cells, once per band.
 111842            cancellationToken.ThrowIfCancellationRequested();
 9011843            for (var x = 0; x < width - 1; x++)
 4394244            {
 4394245                var c0 = cost[y * width + x];
 4394246                var c1 = cost[y * width + x + 1];
 4394247                var c2 = cost[(y + 1) * width + x + 1];
 4394248                var c3 = cost[(y + 1) * width + x];
 49
 4394250                var mask = 0;
 6786651                if (c0 <= band) mask |= 1;
 6786652                if (c1 <= band) mask |= 2;
 6786653                if (c2 <= band) mask |= 4;
 6786654                if (c3 <= band) mask |= 8;
 8332855                if (mask == 0 || mask == 15) continue;
 56
 455657                switch (mask)
 58                {
 27059                    case 1: Add(Bottom, Left); break;
 27460                    case 2: Add(Right, Bottom); break;
 107461                    case 3: Add(Right, Left); break;
 27462                    case 4: Add(Top, Right); break;
 188263                    case 6: Add(Top, Bottom); break;
 52464                    case 7: Add(Top, Left); break;
 27065                    case 8: Add(Left, Top); break;
 189066                    case 9: Add(Bottom, Top); break;
 52067                    case 11: Add(Right, Top); break;
 107468                    case 12: Add(Left, Right); break;
 52069                    case 13: Add(Bottom, Right); break;
 52470                    case 14: Add(Left, Bottom); break;
 71
 72                    // Saddles. The two diagonal corners may be one region pinched through the
 73                    // cell or two separate ones, and the grid cannot tell; the cell's mean
 74                    // decides, which is the usual convention and keeps rings closed either way.
 75                    case 5:
 1276                        if (Centre() <= band) { Add(Bottom, Right); Add(Top, Left); }
 877                        else { Add(Bottom, Left); Add(Top, Right); }
 478                        break;
 79                    case 10:
 1280                        if (Centre() <= band) { Add(Left, Bottom); Add(Right, Top); }
 881                        else { Add(Right, Bottom); Add(Left, Top); }
 482                        break;
 83                }
 84
 455685                continue;
 86
 87                double Centre()
 888                {
 89                    // An unreached corner has no finite cost to average, so the mean is taken
 90                    // over the reached ones only; all four unreached cannot reach a saddle.
 891                    var sum = 0d;
 892                    var n = 0;
 8893                    foreach (var c in stackalloc[] { c0, c1, c2, c3 })
 3294                    {
 4095                        if (c >= double.MaxValue) continue;
 2496                        sum += c;
 2497                        n++;
 2498                    }
 99
 8100                    return n == 0 ? double.MaxValue : sum / n;
 8101                }
 102
 103                void Add(int fromSide, int toSide)
 4564104                {
 4564105                    var from = Crossing(fromSide);
 4564106                    var to = Crossing(toSide);
 9128107                    if (from != to) segments.Add((from, to));
 4564108                }
 109
 110                long Crossing(int side)
 9128111                {
 112                    // Horizontal sides are keyed by the corner left of them, vertical sides by
 113                    // the corner below, so the two cells sharing a side agree on its identity.
 114                    long key;
 115                    double a, b;
 116                    int ax, ay, bx, by;
 9128117                    switch (side)
 118                    {
 21504119                        case Bottom: key = Key(0, x, y); a = c0; b = c1; ax = x; ay = y; bx = x + 1; by = y; break;
 15008120                        case Right: key = Key(1, x + 1, y); a = c1; b = c2; ax = x + 1; ay = y; bx = x + 1; by = y + 1; 
 21504121                        case Top: key = Key(0, x, y + 1); a = c3; b = c2; ax = x; ay = y + 1; bx = x + 1; by = y + 1; br
 15008122                        default: key = Key(1, x, y); a = c0; b = c3; ax = x; ay = y; bx = x; by = y + 1; break;
 123                    }
 124
 9128125                    if (!points.ContainsKey(key))
 4564126                    {
 4564127                        var t = Fraction(a, b, band);
 4564128                        points[key] = (
 4564129                            minLon + (ax + (bx - ax) * t) * lonPerCell,
 4564130                            minLat + (ay + (by - ay) * t) * latPerCell);
 4564131                    }
 132
 9128133                    return key;
 9128134                }
 135            }
 1117136        }
 137
 23138        return Assemble(segments, points, denoise, squareMetersPerSquareDegree, fillHolesBelow);
 139
 9128140        long Key(int kind, int x, int y) => ((long)kind << 60) | ((long)x << 30) | (uint)y;
 23141    }
 142
 143    /// <summary>
 144    /// Where between two corners the band falls. Pinned to the reached corner when the other was
 145    /// never reached: claiming half a cell of ground the search never saw would be an invention.
 146    /// </summary>
 147    private static double Fraction(double a, double b, double band)
 4564148    {
 5871149        if (a >= double.MaxValue) return b >= double.MaxValue ? 0.5 : 1.0;
 4566150        if (b >= double.MaxValue) return 0.0;
 151
 1948152        var span = b - a;
 1948153        if (Math.Abs(span) < double.Epsilon) return 0.5;
 154
 1948155        var t = (band - a) / span;
 1948156        return t < 0 ? 0 : t > 1 ? 1 : t;
 4564157    }
 158
 159    /// <summary>
 160    /// Links segments end to end into rings, then nests holes under the ring containing them.
 161    /// </summary>
 162    private static List<IsochronePolygon> Assemble(List<(long from, long to)> segments,
 163        Dictionary<long, (double longitude, double latitude)> points, double denoise,
 164        double squareMetersPerSquareDegree, double fillHolesBelow)
 23165    {
 23166        var next = new Dictionary<long, long>(segments.Count);
 13761167        foreach (var (from, to) in segments) next[from] = to;
 168
 23169        var rings = new List<IsochroneRing>();
 23170        var used = new HashSet<long>();
 9197171        foreach (var (start, _) in segments)
 4564172        {
 8957173            if (!used.Add(start)) continue;
 174
 171175            var coordinates = new List<(double longitude, double latitude)> { points[start] };
 171176            var at = start;
 4564177            while (next.TryGetValue(at, out var to) && to != start)
 4393178            {
 4393179                if (!used.Add(to)) break;
 4393180                coordinates.Add(points[to]);
 4393181                at = to;
 4393182            }
 183
 184            // Two points cannot enclose anything; a non-closing chain means the grid edge was
 185            // reached, which only happens if the bbox was too tight.
 171186            if (coordinates.Count < 3) continue;
 171187            rings.Add(new IsochroneRing(coordinates, SignedArea(coordinates)));
 171188        }
 189
 23190        if (rings.Count == 0) return [];
 191
 23192        var largest = 0d;
 582193        foreach (var ring in rings) largest = Math.Max(largest, Math.Abs(ring.SignedArea));
 194
 23195        var keep = new List<IsochroneRing>();
 411196        foreach (var ring in rings)
 171197        {
 268198            if (Math.Abs(ring.SignedArea) >= largest * denoise) keep.Add(ring);
 171199        }
 200
 23201        var polygons = new List<IsochronePolygon>();
 23202        var outers = new List<IsochroneRing>();
 23203        var holes = new List<IsochroneRing>();
 263204        foreach (var ring in keep)
 97205        {
 194206            if (ring.SignedArea > 0) outers.Add(ring); else holes.Add(ring);
 97207        }
 208
 23209        var byOuter = new Dictionary<IsochroneRing, List<IsochroneRing>>();
 138210        foreach (var outer in outers) byOuter[outer] = [];
 211
 217212        foreach (var hole in holes)
 74213        {
 214            // Half the shoelace sum is the area; in square degrees until scaled.
 74215            if (fillHolesBelow > 0 && squareMetersPerSquareDegree > 0 &&
 74216                Math.Abs(hole.SignedArea) / 2.0 * squareMetersPerSquareDegree < fillHolesBelow)
 0217            {
 0218                continue;
 219            }
 220
 221            // Smallest container, so a hole inside an island inside a hole lands on the right
 222            // ring rather than the outermost one.
 74223            IsochroneRing? owner = null;
 370224            foreach (var outer in outers)
 74225            {
 74226                if (!Contains(outer, hole.Coordinates[0])) continue;
 74227                if (owner == null || Math.Abs(outer.SignedArea) < Math.Abs(owner.SignedArea))
 74228                    owner = outer;
 74229            }
 230
 148231            if (owner != null) byOuter[owner].Add(hole);
 74232        }
 233
 138234        foreach (var outer in outers) polygons.Add(new IsochronePolygon(outer, byOuter[outer]));
 235
 23236        return polygons;
 23237    }
 238
 239    private static double SignedArea(List<(double longitude, double latitude)> ring)
 171240    {
 171241        var sum = 0d;
 9470242        for (var i = 0; i < ring.Count; i++)
 4564243        {
 4564244            var (x1, y1) = ring[i];
 4564245            var (x2, y2) = ring[(i + 1) % ring.Count];
 4564246            sum += x1 * y2 - x2 * y1;
 4564247        }
 248
 171249        return sum;
 171250    }
 251
 252    private static bool Contains(IsochroneRing ring, (double longitude, double latitude) point)
 74253    {
 74254        var inside = false;
 74255        var coordinates = ring.Coordinates;
 28638256        for (int i = 0, j = coordinates.Count - 1; i < coordinates.Count; j = i++)
 14208257        {
 14208258            var (xi, yi) = coordinates[i];
 14208259            var (xj, yj) = coordinates[j];
 14208260            if (yi > point.latitude != yj > point.latitude &&
 14208261                point.longitude < (xj - xi) * (point.latitude - yi) / (yj - yi) + xi)
 94262            {
 94263                inside = !inside;
 94264            }
 14208265        }
 266
 74267        return inside;
 74268    }
 269}