< Summary

Class:Itinero.Geo.GeoExtensions
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Geo/GeoExtensions.cs
Covered lines:166
Uncovered lines:118
Coverable lines:284
Total lines:555
Line coverage:58.4% (166 of 284)
Covered branches:39
Total branches:96
Branch coverage:40.6% (39 of 96)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
DistanceEstimateInMeter(...)100%1100%
DistanceEstimateInMeterShape(...)100%4100%
DistanceEstimateInMeter(...)100%2100%
OffsetWithDistanceX(...)100%1100%
OffsetWithDistanceY(...)100%1100%
PositionAlongLineInMeters(...)100%10%
PositionAlongLine(...)100%10%
PositionAlongLineInMeters(...)0%100%
PositionAlongLine(...)0%40%
ProjectOn(...)85.71%1491.3%
Center(...)50%470%
Expand(...)0%120%
Intersect(...)27.77%3650%
A(...)100%1100%
B(...)100%1100%
C(...)100%1100%
BoxAround(...)100%1100%
Overlaps(...)100%6100%
AngleWithMeridian(...)75%483.33%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Geo/GeoExtensions.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using Itinero.Geo.Elevation;
 4
 5namespace Itinero.Geo;
 6
 7/// <summary>
 8/// Contains extension methods to work with coordinates, lines, bounding boxes and basic spatial operations.
 9/// </summary>
 10public static class GeoExtensions
 11{
 12    /// <summary>
 13    /// Returns an estimate of the distance between the two given coordinates.
 14    /// </summary>
 15    /// <param name="coordinate1">The first coordinate.</param>
 16    /// <param name="coordinate2">The second coordinate.</param>
 17    /// <remarks>Accuracy decreases with distance.</remarks>
 18    public static double DistanceEstimateInMeter(this (double longitude, double latitude, float? e) coordinate1,
 19        (double longitude, double latitude, float? e) coordinate2)
 107020    {
 107021        var lat1Rad = coordinate1.latitude / 180d * Math.PI;
 107022        var lon1Rad = coordinate1.longitude / 180d * Math.PI;
 107023        var lat2Rad = coordinate2.latitude / 180d * Math.PI;
 107024        var lon2Rad = coordinate2.longitude / 180d * Math.PI;
 25
 107026        var x = (lon2Rad - lon1Rad) * Math.Cos((lat1Rad + lat2Rad) / 2.0);
 107027        var y = lat2Rad - lat1Rad;
 28
 107029        var m = Math.Sqrt((x * x) + (y * y)) * Constants.RadiusOfEarth;
 30
 107031        return m;
 107032    }
 33
 34    internal static double DistanceEstimateInMeterShape(
 35        this (double longitude, double latitude, float? e) coordinate1,
 36        (double longitude, double latitude, float? e) coordinate2,
 37        IEnumerable<(double longitude, double latitude, float? e)>? shape = null)
 4238    {
 4239        if (shape == null)
 3140        {
 3141            return coordinate1.DistanceEstimateInMeter(coordinate2);
 42        }
 43
 1144        var distance = 0.0;
 45
 1146        using var shapeEnumerator = shape.GetEnumerator();
 1147        var previous = coordinate1;
 48
 1549        while (shapeEnumerator.MoveNext())
 450        {
 451            var current = shapeEnumerator.Current;
 452            distance += previous.DistanceEstimateInMeter(current);
 453            previous = current;
 454        }
 55
 1156        distance += previous.DistanceEstimateInMeter(coordinate2);
 57
 1158        return distance;
 4259    }
 60
 61    /// <summary>
 62    /// Returns an estimate of the length of the given linestring.
 63    /// </summary>
 64    /// <param name="lineString">The linestring.</param>
 65    /// <remarks>Accuracy decreases with distance.</remarks>
 66    public static double DistanceEstimateInMeter(
 67        this IEnumerable<(double longitude, double latitude, float? e)> lineString)
 24168    {
 24169        var distance = 0.0;
 70
 24171        using var shapeEnumerator = lineString.GetEnumerator();
 24172        shapeEnumerator.MoveNext();
 24173        var previous = shapeEnumerator.Current;
 74
 56475        while (shapeEnumerator.MoveNext())
 32376        {
 32377            var current = shapeEnumerator.Current;
 32378            distance += previous.DistanceEstimateInMeter(current);
 32379            previous = current;
 32380        }
 81
 24182        return distance;
 24183    }
 84
 85    /// <summary>
 86    /// Returns a coordinate offset with a given distance.
 87    /// </summary>
 88    /// <param name="coordinate">The coordinate.</param>
 89    /// <param name="meter">The distance.</param>
 90    /// <returns>An offset coordinate.</returns>
 91    public static (double longitude, double latitude, float? e) OffsetWithDistanceX(
 92        this (double longitude, double latitude, float? e) coordinate, double meter)
 4693    {
 94        const double offset = 0.001;
 4695        var offsetLon = (coordinate.longitude + offset, coordinate.latitude).AddElevation(coordinate.e);
 4696        var lonDistance = offsetLon.DistanceEstimateInMeter(coordinate);
 97
 4698        return (coordinate.longitude + (meter / lonDistance * offset),
 4699            coordinate.latitude).AddElevation(coordinate.e);
 46100    }
 101
 102    /// <summary>
 103    /// Returns a coordinate offset with a given distance.
 104    /// </summary>
 105    /// <param name="coordinate">The coordinate.</param>
 106    /// <param name="meter">The distance.</param>
 107    /// <returns>An offset coordinate.</returns>
 108    public static (double longitude, double latitude, float? e) OffsetWithDistanceY(
 109        this (double longitude, double latitude, float? e) coordinate,
 110        double meter)
 40111    {
 112        const double offset = 0.001;
 40113        var offsetLat = (coordinate.longitude, coordinate.latitude + offset).AddElevation(coordinate.e);
 40114        var latDistance = offsetLat.DistanceEstimateInMeter(coordinate);
 115
 40116        return (coordinate.longitude,
 40117            coordinate.latitude + (meter / latDistance * offset)).AddElevation(coordinate.e);
 40118    }
 119
 120    /// <summary>
 121    /// Calculates an offset position along the line segment.
 122    /// </summary>
 123    /// <param name="line">The line segment.</param>
 124    /// <param name="position">The position in meters relative to the start point.</param>
 125    /// <returns>The offset coordinate.</returns>
 126    public static (double longitude, double latitude, float? e) PositionAlongLineInMeters(
 127        this IEnumerable<(double longitude, double latitude, float? e)> line, double position)
 0128    {
 129        // ReSharper disable once PossibleMultipleEnumeration
 0130        var length = line.DistanceEstimateInMeter();
 131
 132        // ReSharper disable once PossibleMultipleEnumeration
 0133        return line.PositionAlongLineInMeters(length, position);
 0134    }
 135
 136    /// <summary>
 137    /// Calculates an offset position along the line segment.
 138    /// </summary>
 139    /// <param name="line">The line segment.</param>
 140    /// <param name="offset">The offset [0,1].</param>
 141    /// <returns>The offset coordinate.</returns>
 142    public static (double longitude, double latitude, float? e) PositionAlongLine(
 143        this IEnumerable<(double longitude, double latitude, float? e)> line, double offset)
 0144    {
 145        // ReSharper disable once PossibleMultipleEnumeration
 0146        var length = line.DistanceEstimateInMeter();
 0147        var targetLength = length * (offset / (double)ushort.MaxValue);
 148
 149        // ReSharper disable once PossibleMultipleEnumeration
 0150        return line.PositionAlongLineInMeters(length, targetLength);
 0151    }
 152
 153    private static (double longitude, double latitude, float? e) PositionAlongLineInMeters(
 154        this IEnumerable<(double longitude, double latitude, float? e)> line, double length, double targetLength)
 0155    {
 0156        var currentLength = 0.0;
 157
 158        // ReSharper disable once PossibleMultipleEnumeration
 0159        using var enumerator = line.GetEnumerator();
 0160        if (!enumerator.MoveNext()) throw new Exception("Line doesn't have 2 locations");
 0161        var previous = enumerator.Current;
 0162        while (enumerator.MoveNext())
 0163        {
 0164            var current = enumerator.Current;
 0165            var segmentLength = current.DistanceEstimateInMeter(previous);
 166
 167            // check if the target is in this segment or not.
 0168            if (segmentLength + currentLength < targetLength)
 0169            {
 0170                currentLength += segmentLength;
 0171                previous = current;
 0172                continue;
 173            }
 174
 0175            var segmentOffsetLength = segmentLength + currentLength - targetLength;
 0176            var segmentOffset = 1 - (segmentOffsetLength / segmentLength);
 177
 0178            float? e = null;
 0179            if (previous.e.HasValue &&
 0180                current.e.HasValue)
 0181            {
 0182                e = (float)(previous.e.Value + (segmentOffset * (current.e.Value - previous.e.Value)));
 0183            }
 184
 0185            return (previous.longitude + (segmentOffset * (current.longitude - previous.longitude)),
 0186                previous.latitude + (segmentOffset * (current.latitude - previous.latitude)), e);
 187        }
 188
 0189        return previous;
 0190    }
 191
 192    /// <summary>
 193    /// Calculates an offset position along the line segment.
 194    /// </summary>
 195    /// <param name="line">The line segment.</param>
 196    /// <param name="offset">The offset [0,1].</param>
 197    /// <returns>The offset coordinate.</returns>
 198    public static (double longitude, double latitude, float? e) PositionAlongLine(
 199        this ((double longitude, double latitude, float? e) coordinate1,
 200            (double longitude, double latitude, float? e) coordinate2) line, double offset)
 0201    {
 0202        var coordinate1 = line.coordinate1;
 0203        var coordinate2 = line.coordinate2;
 204
 0205        var latitude = coordinate1.latitude + ((coordinate2.latitude - coordinate1.latitude) * offset);
 0206        var longitude = coordinate1.longitude + ((coordinate2.longitude - coordinate1.longitude) * offset);
 0207        float? e = null;
 0208        if (coordinate1.e.HasValue &&
 0209            coordinate2.e.HasValue)
 0210        {
 0211            e = (float)(coordinate1.e.Value - ((coordinate2.e.Value - coordinate1.e.Value) * offset));
 0212        }
 213
 0214        return (longitude, latitude).AddElevation(e);
 0215    }
 216
 217    private const double E = 0.0000000001;
 218
 219    /// <summary>
 220    /// Projects for coordinate on this line.
 221    /// </summary>
 222    /// <param name="line">The line.</param>
 223    /// <param name="coordinate">The coordinate.</param>
 224    /// <returns>The project coordinate.</returns>
 225    public static (double longitude, double latitude, float? e)? ProjectOn(
 226        this ((double longitude, double latitude, float? e) coordinate1,
 227            (double longitude, double latitude, float? e) coordinate2) line,
 228        (double longitude, double latitude, float? e) coordinate)
 38229    {
 38230        var coordinate1 = line.coordinate1;
 38231        var coordinate2 = line.coordinate2;
 232
 233        // TODO: do we need to calculate the expensive length in meter, this can be done more easily.
 38234        var lengthInMeters = line.coordinate1.DistanceEstimateInMeter(line.coordinate2);
 38235        if (lengthInMeters < E)
 0236        {
 0237            return null;
 238        }
 239
 240        // get direction vector.
 38241        var diffLat = coordinate2.latitude - coordinate1.latitude;
 38242        var diffLon = coordinate2.longitude - coordinate1.longitude;
 243
 244        // increase this line in length if needed.
 38245        var longerLine = line;
 38246        if (lengthInMeters < 50)
 16247        {
 16248            longerLine = (coordinate1, (diffLon + coordinate.longitude, diffLat + coordinate.latitude, null));
 16249        }
 250
 251        // rotate 90°, offset y with x, and x with y.
 38252        var xLength = longerLine.coordinate1.DistanceEstimateInMeter((longerLine.coordinate2.longitude,
 38253            longerLine.coordinate1.latitude, null));
 38254        if (longerLine.coordinate1.longitude > longerLine.coordinate2.longitude)
 10255        {
 10256            xLength = -xLength;
 10257        }
 258
 38259        var yLength = longerLine.coordinate1.DistanceEstimateInMeter((longerLine.coordinate1.longitude,
 38260            longerLine.coordinate2.latitude, null));
 38261        if (longerLine.coordinate1.latitude > longerLine.coordinate2.latitude)
 18262        {
 18263            yLength = -yLength;
 18264        }
 265
 38266        var second = coordinate.OffsetWithDistanceY(xLength)
 38267            .OffsetWithDistanceX(-yLength);
 268
 269        // create a second line.
 38270        var other = (coordinate, second);
 271
 272        // calculate intersection.
 38273        var projected = longerLine.Intersect(other, false);
 274
 275        // check if coordinate is on this line.
 38276        if (!projected.HasValue)
 0277        {
 0278            return null;
 279        }
 280
 281        // check if the coordinate is on this line.
 38282        var dist = (line.A() * line.A()) + (line.B() * line.B());
 38283        var line1 = (projected.Value, coordinate1);
 38284        var distTo1 = (line1.A() * line1.A()) + (line1.B() * line1.B());
 38285        if (distTo1 > dist)
 18286        {
 18287            return null;
 288        }
 289
 20290        var line2 = (projected.Value, coordinate2);
 20291        var distTo2 = (line2.A() * line2.A()) + (line2.B() * line2.B());
 20292        if (distTo2 > dist)
 2293        {
 2294            return null;
 295        }
 296
 18297        return projected;
 38298    }
 299
 300    /// <summary>
 301    /// Returns the center of the box.
 302    /// </summary>
 303    /// <param name="box">The box.</param>
 304    /// <returns>The center.</returns>
 305    public static (double longitude, double latitude, float? e) Center(
 306        this ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 307            bottomRight) box)
 30308    {
 30309        float? e = null;
 30310        if (box.topLeft.e.HasValue &&
 30311            box.bottomRight.e.HasValue)
 0312        {
 0313            e = box.topLeft.e.Value + box.bottomRight.e.Value;
 0314        }
 315
 30316        return ((box.topLeft.longitude + box.bottomRight.longitude) / 2,
 30317            (box.topLeft.latitude + box.bottomRight.latitude) / 2).AddElevation(e);
 30318    }
 319
 320    /// <summary>
 321    /// Expands the given box with the other box to encompass both.
 322    /// </summary>
 323    /// <param name="box">The original box.</param>
 324    /// <param name="other">The other box.</param>
 325    /// <returns>The expand box or the original box if the other was already contained.</returns>
 326    public static ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float?
 327        e) bottomRight)
 328        Expand(
 329            this ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float?
 330                e) bottomRight) box,
 331            ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 332                bottomRight) other)
 0333    {
 0334        if (!box.Overlaps(other.topLeft))
 0335        {
 0336            var center = box.Center();
 337
 338            // handle left.
 0339            var left = box.topLeft.longitude;
 0340            if (!box.Overlaps((other.topLeft.longitude, center.latitude, null)))
 0341            {
 0342                left = other.topLeft.longitude;
 0343            }
 344
 345            // handle top.
 0346            var top = box.topLeft.longitude;
 0347            if (!box.Overlaps((center.longitude, other.topLeft.latitude, null)))
 0348            {
 0349                top = other.topLeft.latitude;
 0350            }
 351
 0352            box = ((left, top, null), box.bottomRight);
 0353        }
 354
 0355        if (!box.Overlaps(other.bottomRight))
 0356        {
 0357            var center = box.Center();
 358
 359            // handle right.
 0360            var right = box.bottomRight.longitude;
 0361            if (!box.Overlaps((other.bottomRight.longitude, center.latitude, null)))
 0362            {
 0363                right = other.bottomRight.longitude;
 0364            }
 365
 366            // handle bottom.
 0367            var bottom = box.bottomRight.latitude;
 0368            if (!box.Overlaps((center.longitude, other.bottomRight.latitude, null)))
 0369            {
 0370                bottom = other.bottomRight.latitude;
 0371            }
 372
 0373            box = (box.topLeft, (right, bottom, null));
 0374        }
 375
 0376        return box;
 0377    }
 378
 379    /// <summary>
 380    /// Calculates the intersection point of the given line with this line.
 381    ///
 382    /// Returns null if the lines have the same direction or don't intersect.
 383    ///
 384    /// Assumes the given line is not a segment and this line is a segment.
 385    /// </summary>
 386    public static (double longitude, double latitude, float? e)? Intersect(
 387        this ((double longitude, double latitude, float? e) coordinate1,
 388            (double longitude, double latitude, float? e) coordinate2) thisLine,
 389        ((double longitude, double latitude, float? e) coordinate1,
 390            (double longitude, double latitude, float? e) coordinate2) line, bool checkSegment = true)
 42391    {
 42392        var det = (double)((line.A() * thisLine.B()) - (thisLine.A() * line.B()));
 42393        if (Math.Abs(det) <= E)
 1394        {
 395            // lines are parallel; no intersections.
 1396            return null;
 397        }
 398        else
 41399        {
 400            // lines are not the same and not parallel so they will intersect.
 41401            var x = ((thisLine.B() * line.C()) - (line.B() * thisLine.C())) / det;
 41402            var y = ((line.A() * thisLine.C()) - (thisLine.A() * line.C())) / det;
 403
 41404            (double latitude, double longitude, float? e) coordinate = (x, y, (float?)null);
 405
 406            // check if the coordinate is on this line.
 41407            if (checkSegment)
 3408            {
 3409                var dist = (thisLine.A() * thisLine.A()) + (thisLine.B() * thisLine.B());
 3410                var line1 = (coordinate, thisLine.coordinate1);
 3411                var distTo1 = (line1.A() * line1.A()) + (line1.B() * line1.B());
 3412                if (distTo1 > dist)
 1413                {
 1414                    return null;
 415                }
 416
 2417                var line2 = (coordinate, thisLine.coordinate2);
 2418                var distTo2 = (line2.A() * line2.A()) + (line2.B() * line2.B());
 2419                if (distTo2 > dist)
 1420                {
 1421                    return null;
 422                }
 1423            }
 424
 39425            if (thisLine.coordinate1.e == null || thisLine.coordinate2.e == null)
 39426            {
 39427                return coordinate;
 428            }
 429
 0430            float? e = null;
 0431            if (Math.Abs(thisLine.coordinate1.e.Value - thisLine.coordinate2.e.Value) < E)
 0432            {
 433                // don't calculate anything, elevation is identical.
 0434                e = thisLine.coordinate1.e;
 0435            }
 0436            else if (Math.Abs(thisLine.A()) < E && Math.Abs(thisLine.B()) < E)
 0437            {
 438                // tiny segment, not stable to calculate offset
 0439                e = thisLine.coordinate1.e;
 0440            }
 441            else
 0442            {
 443                // calculate offset and calculate an estimate of the elevation.
 0444                if (Math.Abs(thisLine.A()) > Math.Abs(thisLine.B()))
 0445                {
 0446                    var diffLat = Math.Abs(thisLine.A());
 0447                    var diffLatIntersection = Math.Abs(coordinate.latitude - thisLine.coordinate1.latitude);
 448
 0449                    e = (float)(((thisLine.coordinate2.e - thisLine.coordinate1.e) *
 0450                                 (diffLatIntersection / diffLat)) +
 0451                                thisLine.coordinate1.e);
 0452                }
 453                else
 0454                {
 0455                    var diffLon = Math.Abs(thisLine.B());
 0456                    var diffLonIntersection = Math.Abs(coordinate.longitude - thisLine.coordinate1.longitude);
 457
 0458                    e = (float)(((thisLine.coordinate2.e - thisLine.coordinate1.e) *
 0459                                 (diffLonIntersection / diffLon)) +
 0460                                thisLine.coordinate1.e);
 0461                }
 0462            }
 463
 0464            return coordinate.AddElevation(e);
 465        }
 42466    }
 467
 468    private static double A(this ((double longitude, double latitude, float? e) coordinate1,
 469        (double longitude, double latitude, float? e) coordinate2) line)
 538470    {
 538471        return line.coordinate2.latitude - line.coordinate1.latitude;
 538472    }
 473
 474    private static double B(this ((double longitude, double latitude, float? e) coordinate1,
 475        (double longitude, double latitude, float? e) coordinate2) line)
 538476    {
 538477        return line.coordinate1.longitude - line.coordinate2.longitude;
 538478    }
 479
 480    private static double C(this ((double longitude, double latitude, float? e) coordinate1,
 481        (double longitude, double latitude, float? e) coordinate2) line)
 164482    {
 164483        return (line.A() * line.coordinate1.longitude) +
 164484               (line.B() * line.coordinate1.latitude);
 164485    }
 486
 487    /// <summary>
 488    /// Creates a box around this coordinate with width/height approximately the given size in meter.
 489    /// </summary>
 490    /// <param name="coordinate">The coordinate.</param>
 491    /// <param name="sizeInMeters">The size in meter.</param>
 492    /// <returns>The size in meter.</returns>
 493    public static ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float?
 494        e) bottomRight)
 495        BoxAround(this (double longitude, double latitude, float? e) coordinate, double sizeInMeters)
 21496    {
 21497        var offsetLat = (coordinate.longitude, coordinate.latitude + 0.1, (float?)null);
 21498        var offsetLon = (coordinate.longitude + 0.1, coordinate.latitude, (float?)null);
 21499        var latDistance = offsetLat.DistanceEstimateInMeter(coordinate);
 21500        var lonDistance = offsetLon.DistanceEstimateInMeter(coordinate);
 501
 21502        return ((coordinate.longitude - (sizeInMeters / lonDistance * 0.1),
 21503                coordinate.latitude + (sizeInMeters / latDistance * 0.1), null),
 21504            (coordinate.longitude + (sizeInMeters / lonDistance * 0.1),
 21505                coordinate.latitude - (sizeInMeters / latDistance * 0.1), null));
 21506    }
 507
 508    /// <summary>
 509    /// Returns true if the box overlaps the given coordinate.
 510    /// </summary>
 511    /// <param name="box">The box.</param>
 512    /// <param name="coordinate">The coordinate.</param>
 513    /// <returns>True of the coordinate is inside the bounding box.</returns>
 514    public static bool Overlaps(
 515        this ((double longitude, double latitude, float? e) topLeft, (double longitude, double latitude, float? e)
 516            bottomRight) box,
 517        (double longitude, double latitude, float? e) coordinate)
 70518    {
 70519        return box.bottomRight.latitude < coordinate.latitude && coordinate.latitude <= box.topLeft.latitude &&
 70520               box.topLeft.longitude < coordinate.longitude && coordinate.longitude <= box.bottomRight.longitude;
 70521    }
 522
 523    /// <summary>
 524    /// Given two WGS84 coordinates, if walking from c1 to c2, it gives the angle that one would be following.
 525    ///
 526    /// 0° is north, 90° is east, -90° is west, both 180 and -180 are south
 527    /// </summary>
 528    /// <param name="c1">The first coordinate.</param>
 529    /// <param name="c2">The second coordinate.</param>
 530    /// <returns>The angle with the meridian in Northern direction.</returns>
 531    public static double AngleWithMeridian(this (double longitude, double latitude, float? e) c1,
 532        (double longitude, double latitude, float? e) c2)
 212533    {
 212534        var dy = c2.latitude - c1.latitude;
 212535        var dx = Math.Cos(Math.PI / 180 * c1.latitude) * (c2.longitude - c1.longitude);
 536        // phi is the angle we search, but with 0 pointing eastwards and in radians
 212537        var phi = Math.Atan2(dy, dx);
 212538        var angle =
 212539            (phi - (Math.PI / 2)) // Rotate 90° to have the north up
 212540            * 180 / Math.PI; // Convert to degrees
 212541        angle = -angle;
 542        // A bit of normalization below:
 212543        if (angle < -180)
 0544        {
 0545            angle += 360;
 0546        }
 547
 212548        if (angle > 180)
 92549        {
 92550            angle -= 360;
 92551        }
 552
 212553        return angle;
 212554    }
 555}