| | | 1 | | using System; |
| | | 2 | | using System.Linq; |
| | | 3 | | using System.Threading; |
| | | 4 | | using System.Threading.Tasks; |
| | | 5 | | using Itinero.Geo; |
| | | 6 | | using Itinero.Network; |
| | | 7 | | using Itinero.Profiles; |
| | | 8 | | using Itinero.Routes; |
| | | 9 | | using Itinero.Routes.Paths; |
| | | 10 | | using Itinero.Routing.Flavours.Dijkstra; |
| | | 11 | | using Itinero.Routing.Flavours.Dijkstra.Bidirectional; |
| | | 12 | | using Itinero.Snapping; |
| | | 13 | | |
| | | 14 | | namespace Itinero.Routing; |
| | | 15 | | |
| | | 16 | | /// <summary> |
| | | 17 | | /// One to one extensions. |
| | | 18 | | /// </summary> |
| | | 19 | | public static class IRouterOneToOneExtensions |
| | | 20 | | { |
| | | 21 | | /// <summary> |
| | | 22 | | /// Calculates the path. |
| | | 23 | | /// </summary> |
| | | 24 | | /// <param name="oneToOneRouter">The router.</param> |
| | | 25 | | /// <param name="cancellationToken"></param> |
| | | 26 | | /// <returns>The path.</returns> |
| | | 27 | | public static async Task<Result<Path>> PathAsync(this IRouterOneToOne oneToOneRouter, |
| | | 28 | | CancellationToken cancellationToken = default) |
| | 70 | 29 | | { |
| | 70 | 30 | | if (oneToOneRouter.Source.direction == null && oneToOneRouter.Target.direction == null && |
| | 70 | 31 | | (!oneToOneRouter.Settings.Profile.TurnCostFactorEnabled || |
| | 70 | 32 | | oneToOneRouter.Settings.BidirectionalWithTurnCosts)) |
| | 65 | 33 | | { |
| | 65 | 34 | | return await oneToOneRouter.CalculateAsync(oneToOneRouter.Source.sp, oneToOneRouter.Target.sp, |
| | 65 | 35 | | cancellationToken); |
| | | 36 | | } |
| | | 37 | | |
| | 5 | 38 | | return (await oneToOneRouter.CalculateAsync([oneToOneRouter.Source], [oneToOneRouter.Target]))[0][0]; |
| | 70 | 39 | | } |
| | | 40 | | |
| | | 41 | | /// <summary> |
| | | 42 | | /// Calculates the route. |
| | | 43 | | /// </summary> |
| | | 44 | | /// <param name="oneToOneRouter">The router.</param> |
| | | 45 | | /// <param name="cancellationToken"></param> |
| | | 46 | | /// <returns>The route.</returns> |
| | | 47 | | public static async Task<Result<Route>> CalculateAsync(this IRouterOneToOne oneToOneRouter, |
| | | 48 | | CancellationToken cancellationToken = default) |
| | 31 | 49 | | { |
| | 31 | 50 | | var path = await oneToOneRouter.PathAsync(cancellationToken); |
| | 31 | 51 | | if (path.IsError) |
| | 15 | 52 | | { |
| | 15 | 53 | | return new Result<Route>(path.ErrorMessage); |
| | | 54 | | } |
| | | 55 | | |
| | 16 | 56 | | return oneToOneRouter.Settings.RouteBuilder.Build(oneToOneRouter.Network, oneToOneRouter.Settings.Profile, |
| | 16 | 57 | | path.Value); |
| | 31 | 58 | | } |
| | | 59 | | |
| | | 60 | | /// <summary> |
| | | 61 | | /// Calculates the weights. |
| | | 62 | | /// </summary> |
| | | 63 | | /// <param name="oneToOneWeightRouter">The router.</param> |
| | | 64 | | /// <returns>The weight</returns> |
| | | 65 | | public static Task<Result<double?>> CalculateAsync(this IRouterWeights<IRouterOneToOne> oneToOneWeightRouter) |
| | 0 | 66 | | { |
| | 0 | 67 | | return Task.FromResult(new Result<double?>("Not implemented")); |
| | | 68 | | |
| | | 69 | | // var profileHandler = oneToOneWeightRouter.Router.Network.GetCostFunctionFor( |
| | | 70 | | // oneToOneWeightRouter.Router.Settings.Profile); |
| | | 71 | | // return oneToOneWeightRouter.Router.Path().Weight(profileHandler.GetForwardWeight); |
| | 0 | 72 | | } |
| | | 73 | | |
| | | 74 | | internal static async Task<Result<Path>> CalculateAsync(this IRouterOneToOne oneToOneRouter, |
| | | 75 | | SnapPoint source, SnapPoint target, CancellationToken cancellationToken) |
| | 65 | 76 | | { |
| | 65 | 77 | | var resolved = await oneToOneRouter.Network.SearchAsync(oneToOneRouter.Settings, source, target, |
| | 65 | 78 | | pruneFactor: 1.0, onForwardRelaxed: null, onBackwardRelaxed: null, cancellationToken); |
| | 75 | 79 | | if (resolved.IsError) return new Result<Path>(resolved.ErrorMessage); |
| | | 80 | | |
| | 55 | 81 | | return resolved.Value.Path; |
| | 65 | 82 | | } |
| | | 83 | | |
| | | 84 | | /// <summary> |
| | | 85 | | /// Routes between two points already snapped, optionally relaxing past the best meeting so a |
| | | 86 | | /// caller can map the region around the route out of the same search. |
| | | 87 | | /// </summary> |
| | | 88 | | /// <param name="pruneFactor">How far past the best meeting to go. 1.0 is an ordinary route.</param> |
| | | 89 | | /// <returns>The route, or an error if the two points are not connected.</returns> |
| | | 90 | | /// <remarks> |
| | | 91 | | /// <see cref="ResolvedRoute.Settled"/> comes back 0: this engine does not count it, only |
| | | 92 | | /// <see cref="ReachabilityRouter"/> does. |
| | | 93 | | /// </remarks> |
| | | 94 | | internal static async Task<Result<ResolvedRoute>> SearchAsync( |
| | | 95 | | this RoutingNetwork network, |
| | | 96 | | RoutingSettings settings, |
| | | 97 | | SnapPoint source, |
| | | 98 | | SnapPoint target, |
| | | 99 | | double pruneFactor, |
| | | 100 | | RelaxedCallback? onForwardRelaxed, |
| | | 101 | | RelaxedCallback? onBackwardRelaxed, |
| | | 102 | | CancellationToken cancellationToken) |
| | 72 | 103 | | { |
| | 72 | 104 | | var profile = settings.Profile; |
| | 72 | 105 | | var costFunction = network.GetCostFunctionFor(profile); |
| | 72 | 106 | | if (settings.CostFunctionWrapper != null) costFunction = settings.CostFunctionWrapper(costFunction); |
| | | 107 | | |
| | 72 | 108 | | var maxBox = settings.MaxBoxFor(network, [source, target]); |
| | | 109 | | |
| | 72 | 110 | | var isMainN = network.GetIsMainNFunc(profile); |
| | 72 | 111 | | var potential = BuildBalancedPotential(network, profile, source, target); |
| | | 112 | | // Rented for this call, returned in the finally. |
| | 72 | 113 | | var search = SearchPool<BidirectionalDijkstra>.Rent(); |
| | | 114 | | Path? result; |
| | | 115 | | double cost; |
| | | 116 | | try |
| | 72 | 117 | | { |
| | 72 | 118 | | (result, cost) = await search.RunAsync(network, source, target, costFunction, |
| | 72 | 119 | | async v => |
| | 1650 | 120 | | { |
| | 1650 | 121 | | if (!network.UsageNotifier.IsVertexDataReady(network, v)) |
| | 0 | 122 | | { |
| | 0 | 123 | | await network.UsageNotifier.NotifyVertex(network, v, cancellationToken); |
| | 0 | 124 | | } |
| | 1650 | 125 | | if (cancellationToken.IsCancellationRequested) return false; |
| | 1650 | 126 | | return CheckMaxDistance(v); |
| | 1650 | 127 | | }, cancellationToken: cancellationToken, isMainN: isMainN, potential: potential, |
| | 72 | 128 | | pruneFactor: pruneFactor, onForwardRelaxed: onForwardRelaxed, |
| | 72 | 129 | | onBackwardRelaxed: onBackwardRelaxed); |
| | 72 | 130 | | } |
| | | 131 | | finally |
| | 72 | 132 | | { |
| | 72 | 133 | | SearchPool<BidirectionalDijkstra>.Return(search); |
| | 72 | 134 | | } |
| | | 135 | | |
| | 82 | 136 | | if (result == null) return new Result<ResolvedRoute>("Path not found"); |
| | | 137 | | |
| | 62 | 138 | | return new ResolvedRoute(result, cost, source, target, costFunction, costFunction, 0); |
| | | 139 | | |
| | | 140 | | bool CheckMaxDistance(VertexId v) |
| | 1650 | 141 | | { |
| | 3300 | 142 | | if (maxBox == null) return false; |
| | | 143 | | |
| | 0 | 144 | | var vertex = network.GetVertex(v); |
| | 0 | 145 | | if (!maxBox.Value.Overlaps(vertex)) |
| | 0 | 146 | | { |
| | 0 | 147 | | return true; |
| | | 148 | | } |
| | | 149 | | |
| | 0 | 150 | | return false; |
| | 1650 | 151 | | } |
| | 72 | 152 | | } |
| | | 153 | | /// <summary> |
| | | 154 | | /// p(v) = (h_target(v) - h_source(v)) / 2, in centimetres; the backward half negates |
| | | 155 | | /// it so the two sum to zero. Null when the profile declares no bound. Halving is what |
| | | 156 | | /// makes them consistent, and why each half gets half the goal-direction of a one-way A*. |
| | | 157 | | /// </summary> |
| | | 158 | | /// <remarks> |
| | | 159 | | /// Internal rather than private because <see cref="ReachabilityRouter"/> needs the same |
| | | 160 | | /// potential. Two routers computing goal direction slightly differently would make their |
| | | 161 | | /// search costs incomparable, and comparing them is the whole point of having both. |
| | | 162 | | /// </remarks> |
| | | 163 | | internal static HeuristicFunc? BuildBalancedPotential(RoutingNetwork network, Profile profile, |
| | | 164 | | SnapPoint source, SnapPoint target) |
| | 101 | 165 | | { |
| | 101 | 166 | | var minFactor = profile.MinFactor; |
| | 201 | 167 | | if (minFactor == 0) return null; |
| | | 168 | | |
| | 1 | 169 | | var sourceLocation = source.LocationOnNetwork(network); |
| | 1 | 170 | | var targetLocation = target.LocationOnNetwork(network); |
| | | 171 | | |
| | 1 | 172 | | return (longitude, latitude) => |
| | 24 | 173 | | { |
| | 24 | 174 | | var from = (longitude, latitude, (float?)null); |
| | 1 | 175 | | |
| | 1 | 176 | | // 1% margin: DistanceEstimateInMeter can slightly overestimate east-west. |
| | 24 | 177 | | var toTarget = from.DistanceEstimateInMeter(targetLocation) * 0.99 * 100.0 * minFactor; |
| | 24 | 178 | | var toSource = from.DistanceEstimateInMeter(sourceLocation) * 0.99 * 100.0 * minFactor; |
| | 24 | 179 | | return (toTarget - toSource) / 2.0; |
| | 25 | 180 | | }; |
| | 101 | 181 | | } |
| | | 182 | | |
| | | 183 | | } |