| | | 1 | | using System.Collections.Generic; |
| | | 2 | | using Itinero.Network; |
| | | 3 | | |
| | | 4 | | namespace Itinero.Routing.Corridors; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// Which endpoint half-edge a corridor edge is, if any. The caller derives the offsets. |
| | | 8 | | /// </summary> |
| | | 9 | | public enum CorridorHalf |
| | | 10 | | { |
| | | 11 | | /// <summary>An ordinary edge, traversed whole.</summary> |
| | | 12 | | None, |
| | | 13 | | |
| | | 14 | | /// <summary>Out of the origin along the source edge, to its head.</summary> |
| | | 15 | | SourceForwardToHead, |
| | | 16 | | |
| | | 17 | | /// <summary>Out of the origin against the source edge, to its tail.</summary> |
| | | 18 | | SourceBackwardToTail, |
| | | 19 | | |
| | | 20 | | /// <summary>Into the destination along the target edge, from its tail.</summary> |
| | | 21 | | TargetForwardFromTail, |
| | | 22 | | |
| | | 23 | | /// <summary>Into the destination against the target edge, from its head.</summary> |
| | | 24 | | TargetBackwardFromHead, |
| | | 25 | | } |
| | | 26 | | |
| | | 27 | | /// <summary> |
| | | 28 | | /// One state: an edge, its traversal direction, and the vertex arrived at. States rather than |
| | | 29 | | /// vertices because turn costs and the local-access rule depend on how a vertex was reached. |
| | | 30 | | /// </summary> |
| | | 31 | | public readonly record struct CorridorState(EdgeId Edge, bool Forward, VertexId Vertex); |
| | | 32 | | |
| | | 33 | | /// <summary> |
| | | 34 | | /// A transition between two corridor states, or between a state and a virtual endpoint node. |
| | | 35 | | /// </summary> |
| | | 36 | | /// <param name="Cost">The head edge's traversal cost plus the turn onto it — not a distance |
| | | 37 | | /// from anything.</param> |
| | | 38 | | /// <param name="Length">Physical length, in the same unit the network reports. For an endpoint |
| | | 39 | | /// half-edge this is the part actually travelled, not the whole edge.</param> |
| | | 40 | | /// <param name="Forward">Which way the edge is travelled, always in path order: tail to head |
| | | 41 | | /// when true, so consecutive edges join head to tail.</param> |
| | | 42 | | public readonly record struct CorridorEdge( |
| | | 43 | | int Tail, |
| | | 44 | | int Head, |
| | | 45 | | double Cost, |
| | | 46 | | double Length, |
| | | 47 | | EdgeId Edge, |
| | | 48 | | bool Forward, |
| | | 49 | | CorridorHalf Half); |
| | | 50 | | |
| | | 51 | | /// <summary> |
| | | 52 | | /// The set of edges that lie on some origin-to-destination path costing no more than a given |
| | | 53 | | /// multiple of the optimum: a cost ellipse around the route, as a graph. |
| | | 54 | | /// </summary> |
| | | 55 | | /// <remarks> |
| | | 56 | | /// Built from the search that answered the route, so it contains that route and prices it the |
| | | 57 | | /// same way. Node 0 is the origin and node 1 the destination; <see cref="States"/> is null at both. |
| | | 58 | | /// </remarks> |
| | | 59 | | public sealed class RouteCorridor |
| | | 60 | | { |
| | 30 | 61 | | internal RouteCorridor( |
| | 30 | 62 | | IReadOnlyList<CorridorState?> states, |
| | 30 | 63 | | IReadOnlyList<CorridorEdge> edges, |
| | 30 | 64 | | double optimalCost, |
| | 30 | 65 | | double optimalLength, |
| | 30 | 66 | | long settled, |
| | 30 | 67 | | int relaxed, |
| | 30 | 68 | | int trimmed, |
| | 30 | 69 | | int fromOrigin, |
| | 30 | 70 | | int interior, |
| | 30 | 71 | | int toDestination, |
| | 30 | 72 | | IReadOnlyList<double> costFromOrigin, |
| | 30 | 73 | | IReadOnlyList<double> costToDestination) |
| | 30 | 74 | | { |
| | 30 | 75 | | this.States = states; |
| | 30 | 76 | | this.Edges = edges; |
| | 30 | 77 | | this.OptimalCost = optimalCost; |
| | 30 | 78 | | this.OptimalLength = optimalLength; |
| | 30 | 79 | | this.Settled = settled; |
| | 30 | 80 | | this.Relaxed = relaxed; |
| | 30 | 81 | | this.Trimmed = trimmed; |
| | 30 | 82 | | this.FromOrigin = fromOrigin; |
| | 30 | 83 | | this.Interior = interior; |
| | 30 | 84 | | this.ToDestination = toDestination; |
| | 30 | 85 | | this.CostFromOrigin = costFromOrigin; |
| | 30 | 86 | | this.CostToDestination = costToDestination; |
| | 30 | 87 | | } |
| | | 88 | | |
| | | 89 | | /// <summary>The origin node's index.</summary> |
| | | 90 | | public const int SourceNode = 0; |
| | | 91 | | |
| | | 92 | | /// <summary>The destination node's index.</summary> |
| | | 93 | | public const int TargetNode = 1; |
| | | 94 | | |
| | | 95 | | /// <summary>States by node index; null at the two virtual endpoints.</summary> |
| | 36 | 96 | | public IReadOnlyList<CorridorState?> States { get; } |
| | | 97 | | |
| | | 98 | | /// <summary>The corridor's edges, in no particular order.</summary> |
| | 2363 | 99 | | public IReadOnlyList<CorridorEdge> Edges { get; } |
| | | 100 | | |
| | | 101 | | /// <summary>What the optimal route cost — the cost the corridor's budget is a multiple of.</summary> |
| | 14 | 102 | | public double OptimalCost { get; } |
| | | 103 | | |
| | | 104 | | /// <summary>The optimal route's physical length.</summary> |
| | 0 | 105 | | public double OptimalLength { get; } |
| | | 106 | | |
| | | 107 | | /// <summary>States the route search settled, both halves. Diagnostic.</summary> |
| | 0 | 108 | | public long Settled { get; } |
| | | 109 | | |
| | | 110 | | /// <summary>Transitions examined before filtering. Diagnostic.</summary> |
| | 0 | 111 | | public int Relaxed { get; } |
| | | 112 | | |
| | | 113 | | /// <summary>Edges that priced inside the budget but led nowhere. Small; large means the |
| | | 114 | | /// halves disagree about more than their endpoints' surroundings.</summary> |
| | 0 | 115 | | public int Trimmed { get; } |
| | | 116 | | |
| | | 117 | | /// <summary> |
| | | 118 | | /// Edges out of the origin before the trim. With <see cref="Interior"/> and |
| | | 119 | | /// <see cref="ToDestination"/>, says which stage an empty corridor came up short at. |
| | | 120 | | /// </summary> |
| | 0 | 121 | | public int FromOrigin { get; } |
| | | 122 | | |
| | | 123 | | /// <summary>Edges between two states that passed the cost filter, before the trim.</summary> |
| | 0 | 124 | | public int Interior { get; } |
| | | 125 | | |
| | | 126 | | /// <summary>Edges into the destination that passed the cost filter, before the trim.</summary> |
| | 1 | 127 | | public int ToDestination { get; } |
| | | 128 | | |
| | | 129 | | /// <summary> |
| | | 130 | | /// What it costs to reach each node from the origin — the shortest-path potential over the |
| | | 131 | | /// corridor, in the direction of travel. |
| | | 132 | | /// </summary> |
| | | 133 | | /// <remarks> |
| | | 134 | | /// With <see cref="CostToDestination"/>, <c>CostFromOrigin[tail] + cost + |
| | | 135 | | /// CostToDestination[head]</c> is the cheapest path through an edge — what the filter tested. |
| | | 136 | | /// </remarks> |
| | 220 | 137 | | public IReadOnlyList<double> CostFromOrigin { get; } |
| | | 138 | | |
| | | 139 | | /// <summary> |
| | | 140 | | /// What it costs to carry on to the destination from each node — the shortest-path potential |
| | | 141 | | /// over the corridor, computed by the filter and worth keeping rather than recomputing. |
| | | 142 | | /// </summary> |
| | 440 | 143 | | public IReadOnlyList<double> CostToDestination { get; } |
| | | 144 | | } |