| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Threading; |
| | | 4 | | using System.Threading.Tasks; |
| | | 5 | | using Itinero.Geo; |
| | | 6 | | using Itinero.Geo.Directions; |
| | | 7 | | using Itinero.Network; |
| | | 8 | | using Itinero.Profiles; |
| | | 9 | | using Itinero.Routes.Paths; |
| | | 10 | | using Itinero.Routing.Alternatives; |
| | | 11 | | using Itinero.Routing.Costs; |
| | | 12 | | using Itinero.Routing.Flavours.Dijkstra; |
| | | 13 | | using Itinero.Snapping; |
| | | 14 | | |
| | | 15 | | namespace Itinero.Routing; |
| | | 16 | | |
| | | 17 | | /// <summary> |
| | | 18 | | /// Contains extensions for the IRouter interface. |
| | | 19 | | /// </summary> |
| | | 20 | | public static class IRouterExtensions |
| | | 21 | | { |
| | | 22 | | /// <summary> |
| | | 23 | | /// Configures the router to route from the given point. |
| | | 24 | | /// </summary> |
| | | 25 | | /// <param name="router">The router.</param> |
| | | 26 | | /// <param name="snapPoint">The point to route from.</param> |
| | | 27 | | /// <returns>A configured router.</returns> |
| | | 28 | | public static IHasSource From(this IRouter router, SnapPoint snapPoint) |
| | 11618 | 29 | | { |
| | 11618 | 30 | | return router.From((snapPoint, (bool?)null)); |
| | 11618 | 31 | | } |
| | | 32 | | |
| | | 33 | | /// <summary> |
| | | 34 | | /// Configures the router to route from the given point. |
| | | 35 | | /// </summary> |
| | | 36 | | /// <param name="router">The router.</param> |
| | | 37 | | /// <param name="directedSnapPoint">The point to route from.</param> |
| | | 38 | | /// <returns>A configured router.</returns> |
| | | 39 | | public static IHasSource From(this IRouter router, (SnapPoint snapPoint, bool? direction) directedSnapPoint) |
| | 11619 | 40 | | { |
| | 11619 | 41 | | return new Router(router.Network, router.Settings) |
| | 11619 | 42 | | { |
| | 11619 | 43 | | Source = directedSnapPoint |
| | 11619 | 44 | | }; |
| | 11619 | 45 | | } |
| | | 46 | | |
| | | 47 | | /// <summary> |
| | | 48 | | /// Configures the router to route from the given point. |
| | | 49 | | /// </summary> |
| | | 50 | | /// <param name="router">The router.</param> |
| | | 51 | | /// <param name="directedSnapPoint">The point to route from.</param> |
| | | 52 | | /// <returns>A configured router.</returns> |
| | | 53 | | public static IHasSource From(this IRouter router, |
| | | 54 | | (SnapPoint snapPoint, DirectionEnum? direction) directedSnapPoint) |
| | 0 | 55 | | { |
| | 0 | 56 | | return router.From(directedSnapPoint.ToDirected(router.Network)); |
| | 0 | 57 | | } |
| | | 58 | | |
| | | 59 | | /// <summary> |
| | | 60 | | /// Configures the router to route from the given point. |
| | | 61 | | /// </summary> |
| | | 62 | | /// <param name="router">The router.</param> |
| | | 63 | | /// <param name="snapPoints">The points to route from.</param> |
| | | 64 | | /// <returns>A configured router.</returns> |
| | | 65 | | public static IHasSources From(this IRouter router, IReadOnlyList<SnapPoint> snapPoints) |
| | 0 | 66 | | { |
| | 0 | 67 | | return router.From(snapPoints.ToDirected()); |
| | 0 | 68 | | } |
| | | 69 | | |
| | | 70 | | /// <summary> |
| | | 71 | | /// Configures the router to route from the given point. |
| | | 72 | | /// </summary> |
| | | 73 | | /// <param name="router">The router.</param> |
| | | 74 | | /// <param name="directedSnapPoints">The points to route from.</param> |
| | | 75 | | /// <returns>A configured router.</returns> |
| | | 76 | | public static IHasSources From(this IRouter router, |
| | | 77 | | IReadOnlyList<(SnapPoint snapPoint, DirectionEnum? direction)> directedSnapPoints) |
| | 0 | 78 | | { |
| | 0 | 79 | | return router.From(directedSnapPoints.ToDirected(router.Network)); |
| | 0 | 80 | | } |
| | | 81 | | |
| | | 82 | | /// <summary> |
| | | 83 | | /// Configures the router to route from the given point. |
| | | 84 | | /// </summary> |
| | | 85 | | /// <param name="router">The router.</param> |
| | | 86 | | /// <param name="directedSnapPoints">The points to route from.</param> |
| | | 87 | | /// <returns>A configured router.</returns> |
| | | 88 | | public static IHasSources From(this IRouter router, |
| | | 89 | | IReadOnlyList<(SnapPoint snapPoint, bool? direction)> directedSnapPoints) |
| | 0 | 90 | | { |
| | 0 | 91 | | return new Router(router.Network, router.Settings) |
| | 0 | 92 | | { |
| | 0 | 93 | | Sources = directedSnapPoints |
| | 0 | 94 | | }; |
| | 0 | 95 | | } |
| | | 96 | | |
| | | 97 | | internal static async Task<IReadOnlyList<IReadOnlyList<Result<Path>>>> CalculateAsync(this IRouter manyToManyRouter, |
| | | 98 | | IReadOnlyList<SnapPoint> sources, IReadOnlyList<SnapPoint> targets, CancellationToken cancellationToken) |
| | 11542 | 99 | | { |
| | 11542 | 100 | | var settings = manyToManyRouter.Settings; |
| | 11542 | 101 | | var routingNetwork = manyToManyRouter.Network; |
| | | 102 | | |
| | 11542 | 103 | | var profile = settings.Profile; |
| | 11542 | 104 | | var costFunction = routingNetwork.GetCostFunctionFor(profile); |
| | 11542 | 105 | | if (settings.CostFunctionWrapper != null) costFunction = settings.CostFunctionWrapper(costFunction); |
| | | 106 | | |
| | 11542 | 107 | | var maxBox = settings.MaxBoxFor(routingNetwork, sources); |
| | | 108 | | |
| | | 109 | | bool CheckMaxDistance(VertexId v) |
| | 304245 | 110 | | { |
| | 304245 | 111 | | if (maxBox == null) |
| | 4 | 112 | | { |
| | 4 | 113 | | return false; |
| | | 114 | | } |
| | | 115 | | |
| | 304241 | 116 | | if (routingNetwork == null) |
| | 0 | 117 | | { |
| | 0 | 118 | | throw new Exception("Router cannot be null here."); |
| | | 119 | | } |
| | | 120 | | |
| | 304241 | 121 | | var vertex = routingNetwork.GetVertex(v); |
| | 304241 | 122 | | if (!maxBox.Value.Overlaps(vertex)) |
| | 51273 | 123 | | { |
| | 51273 | 124 | | return true; |
| | | 125 | | } |
| | | 126 | | |
| | 252968 | 127 | | return false; |
| | 304245 | 128 | | } |
| | | 129 | | |
| | 11542 | 130 | | var heuristic = BuildHeuristic(routingNetwork, profile, targets); |
| | 11542 | 131 | | var isMainN = routingNetwork.GetIsMainNFunc(profile); |
| | 11542 | 132 | | var results = new IReadOnlyList<Result<Path>>[sources.Count]; |
| | 46168 | 133 | | for (var s = 0; s < sources.Count; s++) |
| | 11542 | 134 | | { |
| | 11542 | 135 | | var source = sources[s]; |
| | 11542 | 136 | | var search = Flavours.Dijkstra.SearchPool<Flavours.Dijkstra.Dijkstra>.Rent(); |
| | | 137 | | (Path? path, double cost)[] pathsAndCosts; |
| | | 138 | | try |
| | 11542 | 139 | | { |
| | 11542 | 140 | | pathsAndCosts = await search.RunAsync(routingNetwork, source, targets, |
| | 11542 | 141 | | costFunction.GetDijkstraWeightFunc(), |
| | 11542 | 142 | | async v => |
| | 304245 | 143 | | { |
| | 304245 | 144 | | if (!routingNetwork.UsageNotifier.IsVertexDataReady(routingNetwork, v.vertexId)) |
| | 0 | 145 | | { |
| | 0 | 146 | | await routingNetwork.UsageNotifier.NotifyVertex(routingNetwork, v.vertexId, cancellationToke |
| | 0 | 147 | | } |
| | 304245 | 148 | | return CheckMaxDistance(v.vertexId); |
| | 315787 | 149 | | }, isMainN: isMainN, heuristic: heuristic); |
| | 11542 | 150 | | } |
| | | 151 | | finally |
| | 11542 | 152 | | { |
| | 11542 | 153 | | Flavours.Dijkstra.SearchPool<Flavours.Dijkstra.Dijkstra>.Return(search); |
| | 11542 | 154 | | } |
| | | 155 | | |
| | 11542 | 156 | | var sourceResults = new Result<Path>[pathsAndCosts.Length]; |
| | 402636 | 157 | | for (var r = 0; r < sourceResults.Length; r++) |
| | 189776 | 158 | | { |
| | 189776 | 159 | | var (path, _) = pathsAndCosts[r]; |
| | 189776 | 160 | | if (path == null) |
| | 59484 | 161 | | { |
| | 59484 | 162 | | sourceResults[r] = new Result<Path>("Path not found!"); |
| | 59484 | 163 | | } |
| | | 164 | | else |
| | 130292 | 165 | | { |
| | 130292 | 166 | | sourceResults[r] = path; |
| | 130292 | 167 | | } |
| | 189776 | 168 | | } |
| | | 169 | | |
| | 11542 | 170 | | results[s] = sourceResults; |
| | 11542 | 171 | | } |
| | | 172 | | |
| | 11542 | 173 | | return results; |
| | 11542 | 174 | | } |
| | | 175 | | |
| | | 176 | | internal static async Task<IReadOnlyList<IReadOnlyList<Result<Path>>>> CalculateAsync(this IRouter manyToManyRouter, |
| | | 177 | | IReadOnlyList<(SnapPoint snapPoint, bool? direction)> sources, |
| | | 178 | | IReadOnlyList<(SnapPoint snapPoint, bool? direction)> targets) |
| | 5 | 179 | | { |
| | 5 | 180 | | var settings = manyToManyRouter.Settings; |
| | 5 | 181 | | var routerDb = manyToManyRouter.Network; |
| | | 182 | | |
| | 5 | 183 | | var profile = settings.Profile; |
| | 5 | 184 | | var costFunction = routerDb.GetCostFunctionFor(profile); |
| | 5 | 185 | | if (settings.CostFunctionWrapper != null) costFunction = settings.CostFunctionWrapper(costFunction); |
| | | 186 | | |
| | 5 | 187 | | var maxBox = settings.MaxBoxFor(routerDb, sources); |
| | | 188 | | |
| | | 189 | | bool CheckMaxDistance(VertexId v) |
| | 12 | 190 | | { |
| | 12 | 191 | | if (maxBox == null) |
| | 12 | 192 | | { |
| | 12 | 193 | | return false; |
| | | 194 | | } |
| | | 195 | | |
| | 0 | 196 | | if (routerDb == null) |
| | 0 | 197 | | { |
| | 0 | 198 | | throw new Exception("Router cannot be null here."); |
| | | 199 | | } |
| | | 200 | | |
| | 0 | 201 | | var vertex = routerDb.GetVertex(v); |
| | 0 | 202 | | if (!maxBox.Value.Overlaps(vertex)) |
| | 0 | 203 | | { |
| | 0 | 204 | | return true; |
| | | 205 | | } |
| | | 206 | | |
| | 0 | 207 | | return false; |
| | 12 | 208 | | } |
| | | 209 | | |
| | 5 | 210 | | var heuristic = BuildHeuristic(routerDb, profile, targets); |
| | 5 | 211 | | var isMainN = routerDb.GetIsMainNFunc(profile); |
| | 5 | 212 | | var results = new IReadOnlyList<Result<Path>>[sources.Count]; |
| | 20 | 213 | | for (var s = 0; s < sources.Count; s++) |
| | 5 | 214 | | { |
| | 5 | 215 | | var source = sources[s]; |
| | 5 | 216 | | var search = Flavours.Dijkstra.SearchPool<Flavours.Dijkstra.Dijkstra>.Rent(); |
| | | 217 | | (Path? path, double cost)[] paths; |
| | | 218 | | try |
| | 5 | 219 | | { |
| | 5 | 220 | | paths = await search.RunAsync(routerDb, source, targets, |
| | 5 | 221 | | costFunction.GetDijkstraWeightFunc(), |
| | 5 | 222 | | async e => |
| | 12 | 223 | | { |
| | 12 | 224 | | if (!routerDb.UsageNotifier.IsVertexDataReady(routerDb, e.vertexId)) |
| | 0 | 225 | | { |
| | 0 | 226 | | await routerDb.UsageNotifier.NotifyVertex(routerDb, e.vertexId); |
| | 0 | 227 | | } |
| | 12 | 228 | | return CheckMaxDistance(e.vertexId); |
| | 17 | 229 | | }, isMainN: isMainN, heuristic: heuristic); |
| | 5 | 230 | | } |
| | | 231 | | finally |
| | 5 | 232 | | { |
| | 5 | 233 | | Flavours.Dijkstra.SearchPool<Flavours.Dijkstra.Dijkstra>.Return(search); |
| | 5 | 234 | | } |
| | | 235 | | |
| | 5 | 236 | | var sourceResults = new Result<Path>[paths.Length]; |
| | 20 | 237 | | for (var r = 0; r < sourceResults.Length; r++) |
| | 5 | 238 | | { |
| | 5 | 239 | | var (path, _) = paths[r]; |
| | 5 | 240 | | if (path == null) |
| | 5 | 241 | | { |
| | 5 | 242 | | sourceResults[r] = new Result<Path>("Routes not found!"); |
| | 5 | 243 | | } |
| | | 244 | | else |
| | 0 | 245 | | { |
| | 0 | 246 | | sourceResults[r] = path; |
| | 0 | 247 | | } |
| | 5 | 248 | | } |
| | | 249 | | |
| | 5 | 250 | | results[s] = sourceResults; |
| | 5 | 251 | | } |
| | | 252 | | |
| | 5 | 253 | | return results; |
| | 5 | 254 | | } |
| | | 255 | | |
| | | 256 | | /// <summary> |
| | | 257 | | /// Builds the A* estimate — straight-line distance to the nearest target × |
| | | 258 | | /// <see cref="Profile.MinFactor"/>, in centimetres — or null when the profile |
| | | 259 | | /// declares no bound and the search should stay plain Dijkstra. |
| | | 260 | | /// </summary> |
| | | 261 | | private static HeuristicFunc? BuildHeuristic(RoutingNetwork network, Profile profile, |
| | | 262 | | IReadOnlyList<(SnapPoint snapPoint, bool? direction)> targets) |
| | 5 | 263 | | { |
| | 5 | 264 | | var points = new SnapPoint[targets.Count]; |
| | 25 | 265 | | for (var i = 0; i < targets.Count; i++) points[i] = targets[i].snapPoint; |
| | | 266 | | |
| | 5 | 267 | | return BuildHeuristic(network, profile, points); |
| | 5 | 268 | | } |
| | | 269 | | |
| | | 270 | | private static HeuristicFunc? BuildHeuristic(RoutingNetwork network, Profile profile, |
| | | 271 | | IReadOnlyList<SnapPoint> targets) |
| | 11547 | 272 | | { |
| | 11547 | 273 | | var minFactor = profile.MinFactor; |
| | 23094 | 274 | | if (minFactor == 0) return null; |
| | 0 | 275 | | if (targets.Count == 0) return null; |
| | | 276 | | |
| | 0 | 277 | | var targetLocations = new (double longitude, double latitude, float? e)[targets.Count]; |
| | 0 | 278 | | for (var t = 0; t < targets.Count; t++) |
| | 0 | 279 | | { |
| | 0 | 280 | | targetLocations[t] = targets[t].LocationOnNetwork(network); |
| | 0 | 281 | | } |
| | | 282 | | |
| | 0 | 283 | | return (longitude, latitude) => |
| | 0 | 284 | | { |
| | 0 | 285 | | var from = (longitude, latitude, (float?)null); |
| | 0 | 286 | | |
| | 0 | 287 | | var nearest = double.MaxValue; |
| | 0 | 288 | | foreach (var target in targetLocations) |
| | 0 | 289 | | { |
| | 0 | 290 | | var distance = from.DistanceEstimateInMeter(target); |
| | 0 | 291 | | if (distance < nearest) nearest = distance; |
| | 0 | 292 | | } |
| | 0 | 293 | | |
| | 0 | 294 | | // 1% margin: DistanceEstimateInMeter is equirectangular and can slightly |
| | 0 | 295 | | // overestimate east-west, which would make the bound inadmissible. |
| | 0 | 296 | | return nearest * 0.99 * 100.0 * minFactor; |
| | 0 | 297 | | }; |
| | 11547 | 298 | | } |
| | | 299 | | |
| | | 300 | | } |