| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Linq; |
| | | 4 | | using System.Runtime.CompilerServices; |
| | | 5 | | using System.Threading; |
| | | 6 | | using System.Threading.Tasks; |
| | | 7 | | using Itinero.Geo; |
| | | 8 | | using Itinero.Network; |
| | | 9 | | using Itinero.Network.Enumerators.Edges; |
| | | 10 | | using Itinero.Network.Search.Edges; |
| | | 11 | | using Itinero.Network.Search.Islands; |
| | | 12 | | using Itinero.Profiles; |
| | | 13 | | using Itinero.Routing.Costs; |
| | | 14 | | |
| | | 15 | | namespace Itinero.Snapping; |
| | | 16 | | |
| | | 17 | | /// <summary> |
| | | 18 | | /// Just like the `Snapper`, it'll snap to a location. |
| | | 19 | | /// However, the 'Snapper' will match to any road whereas the `LocationSnapper` will only snap to roads accessible to th |
| | | 20 | | /// </summary> |
| | | 21 | | internal sealed class Snapper : ISnapper, IEdgeChecker |
| | | 22 | | { |
| | | 23 | | private readonly RoutingNetwork _routingNetwork; |
| | | 24 | | private readonly bool _anyProfile; |
| | | 25 | | private readonly bool _checkCanStopOn; |
| | | 26 | | private readonly double _offsetInMeter; |
| | | 27 | | private readonly double _offsetInMeterMax; |
| | | 28 | | private readonly double _maxDistance; |
| | | 29 | | private readonly Islands[] _islands; |
| | | 30 | | private readonly ICostFunction[] _costFunctions; |
| | | 31 | | private readonly Profile[] _profiles; |
| | | 32 | | |
| | | 33 | | // One directed-graph pair per profile, for the lifetime of this snapper |
| | | 34 | | private readonly IslandDirectedGraph?[] _islandDgFull; |
| | | 35 | | private readonly IslandDirectedGraph?[] _islandDgNonLocal; |
| | | 36 | | |
| | | 37 | | // Whether a candidate has to be connected to the wider network, or only usable by the |
| | | 38 | | // profile. Off means access and can-stop-on still apply but nothing asks where the edge |
| | | 39 | | // leads — the caller has taken that question on itself. |
| | | 40 | | private readonly bool _checkConnectivity; |
| | | 41 | | |
| | 236 | 42 | | public Snapper(RoutingNetwork routingNetwork, IEnumerable<Profile> profiles, SnapperSettings settings) |
| | 236 | 43 | | { |
| | 236 | 44 | | _routingNetwork = routingNetwork; |
| | 236 | 45 | | _anyProfile = settings.AnyProfile; |
| | 236 | 46 | | _checkCanStopOn = settings.CheckCanStopOn; |
| | 236 | 47 | | _offsetInMeter = settings.OffsetInMeter; |
| | 236 | 48 | | _offsetInMeterMax = settings.OffsetInMeterMax; |
| | 236 | 49 | | _maxDistance = settings.MaxDistance; |
| | 236 | 50 | | _checkConnectivity = settings.CheckIslands; |
| | 236 | 51 | | _profiles = profiles.ToArray(); |
| | | 52 | | |
| | 236 | 53 | | _costFunctions = _profiles.Select(_routingNetwork.GetCostFunctionFor).ToArray(); |
| | 236 | 54 | | _islands = !_checkConnectivity || routingNetwork.IslandManager.MaxIslandSize == 0 |
| | 236 | 55 | | ? [] |
| | 244 | 56 | | : _profiles.Select(p => _routingNetwork.IslandManager.GetIslandsFor(p)).ToArray(); |
| | 236 | 57 | | _islandDgFull = new IslandDirectedGraph?[_profiles.Length]; |
| | 236 | 58 | | _islandDgNonLocal = new IslandDirectedGraph?[_profiles.Length]; |
| | 236 | 59 | | } |
| | | 60 | | |
| | | 61 | | /// <inheritdoc/> |
| | | 62 | | public async IAsyncEnumerable<Result<SnapPoint>> ToAsync(VertexId vertexId, bool asDeparture = true) |
| | 59 | 63 | | { |
| | 59 | 64 | | var enumerator = _routingNetwork.GetEdgeEnumerator(); |
| | 59 | 65 | | RoutingNetworkEdgeEnumerator? secondEnumerator = null; |
| | | 66 | | |
| | 59 | 67 | | if (!enumerator.MoveTo(vertexId)) |
| | 1 | 68 | | { |
| | 1 | 69 | | yield break; |
| | | 70 | | } |
| | | 71 | | |
| | 62 | 72 | | while (enumerator.MoveNext()) |
| | 59 | 73 | | { |
| | 59 | 74 | | if (_costFunctions.Length == 0) |
| | 59 | 75 | | { |
| | 59 | 76 | | if (enumerator.Forward) |
| | 32 | 77 | | { |
| | 32 | 78 | | yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0)); |
| | 2 | 79 | | } |
| | | 80 | | else |
| | 27 | 81 | | { |
| | 27 | 82 | | yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue)); |
| | 2 | 83 | | } |
| | 4 | 84 | | } |
| | | 85 | | else |
| | 0 | 86 | | { |
| | 0 | 87 | | if (asDeparture) |
| | 0 | 88 | | { |
| | 0 | 89 | | if (!(this.IsAcceptable(enumerator) ?? await (this as IEdgeChecker).RunCheckAsync(enumerator, defaul |
| | 0 | 90 | | { |
| | | 91 | | |
| | 0 | 92 | | continue; |
| | | 93 | | } |
| | | 94 | | |
| | 0 | 95 | | if (enumerator.Forward) |
| | 0 | 96 | | { |
| | 0 | 97 | | yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0)); |
| | 0 | 98 | | } |
| | | 99 | | else |
| | 0 | 100 | | { |
| | 0 | 101 | | yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue)); |
| | 0 | 102 | | } |
| | 0 | 103 | | } |
| | | 104 | | else |
| | 0 | 105 | | { |
| | 0 | 106 | | secondEnumerator ??= _routingNetwork.GetEdgeEnumerator(); |
| | 0 | 107 | | secondEnumerator.MoveTo(enumerator.EdgeId, !enumerator.Forward); |
| | 0 | 108 | | if (!(this.IsAcceptable(secondEnumerator) ?? await (this as IEdgeChecker).RunCheckAsync(secondEnumer |
| | 0 | 109 | | { |
| | 0 | 110 | | continue; |
| | | 111 | | } |
| | | 112 | | |
| | 0 | 113 | | if (enumerator.Forward) |
| | 0 | 114 | | { |
| | 0 | 115 | | yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, 0)); |
| | 0 | 116 | | } |
| | | 117 | | else |
| | 0 | 118 | | { |
| | 0 | 119 | | yield return new Result<SnapPoint>(new SnapPoint(enumerator.EdgeId, ushort.MaxValue)); |
| | 0 | 120 | | } |
| | 0 | 121 | | } |
| | 0 | 122 | | } |
| | 4 | 123 | | } |
| | 59 | 124 | | } |
| | | 125 | | |
| | | 126 | | /// <inheritdoc/> |
| | | 127 | | public async Task<Result<SnapPoint>> ToAsync(EdgeId edgeId, ushort offset, bool forward = true) |
| | 0 | 128 | | { |
| | 0 | 129 | | var enumerator = _routingNetwork.GetEdgeEnumerator(); |
| | | 130 | | |
| | 0 | 131 | | if (!enumerator.MoveTo(edgeId, forward)) return new Result<SnapPoint>("Edge not found"); |
| | | 132 | | |
| | 0 | 133 | | if (!(this.IsAcceptable(enumerator) ?? await (this as IEdgeChecker).RunCheckAsync(enumerator, default))) |
| | 0 | 134 | | return new Result<SnapPoint>("Edge cannot be snapped to by configured profiles in the given direction"); |
| | | 135 | | |
| | 0 | 136 | | return new Result<SnapPoint>(new SnapPoint(edgeId, offset)); |
| | 0 | 137 | | } |
| | | 138 | | |
| | | 139 | | /// <inheritdoc/> |
| | | 140 | | public async Task<Result<SnapPoint>> ToAsync( |
| | | 141 | | double longitude, double latitude, |
| | | 142 | | CancellationToken cancellationToken = default) |
| | 110 | 143 | | { |
| | 110 | 144 | | (double longitude, double latitude, float? e) location = (longitude, latitude, null); |
| | | 145 | | |
| | | 146 | | // First load region. |
| | 110 | 147 | | var box = location.BoxAround(_offsetInMeter); |
| | 110 | 148 | | await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken); |
| | | 149 | | |
| | | 150 | | // Iterate over the MaxDistance schedule (50, 200, 800, …, MaxDistance). |
| | | 151 | | // Most snaps land on the first small-D pass; sparse-area / no-snap |
| | | 152 | | // cases escalate through the schedule. PR2's tile + vertex predicates |
| | | 153 | | // make small-D passes nearly free because almost every tile in the |
| | | 154 | | // load box is excluded. |
| | 458 | 155 | | foreach (var d in ExpandSchedule(_maxDistance)) |
| | 116 | 156 | | { |
| | 116 | 157 | | var snapPoint = await _routingNetwork.SnapInBoxAsync(box, this, maxDistance: d, cancellationToken); |
| | 220 | 158 | | if (snapPoint.EdgeId != EdgeId.Empty) return snapPoint; |
| | 12 | 159 | | if (cancellationToken.IsCancellationRequested) break; |
| | 12 | 160 | | } |
| | | 161 | | |
| | | 162 | | // Retry once with a larger load region — same role as today. |
| | 6 | 163 | | if (!(_offsetInMeter < _offsetInMeterMax)) |
| | 2 | 164 | | { |
| | 2 | 165 | | return new Result<SnapPoint>( |
| | 2 | 166 | | FormattableString.Invariant($"Could not snap to location: {location.longitude},{location.latitude}")); |
| | | 167 | | } |
| | | 168 | | |
| | 4 | 169 | | box = location.BoxAround(_offsetInMeterMax); |
| | 4 | 170 | | await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken); |
| | | 171 | | |
| | 24 | 172 | | foreach (var d in ExpandSchedule(_maxDistance)) |
| | 7 | 173 | | { |
| | 7 | 174 | | var snapPoint = await _routingNetwork.SnapInBoxAsync(box, this, maxDistance: d, cancellationToken); |
| | 9 | 175 | | if (snapPoint.EdgeId != EdgeId.Empty) return snapPoint; |
| | 5 | 176 | | if (cancellationToken.IsCancellationRequested) break; |
| | 5 | 177 | | } |
| | | 178 | | |
| | 2 | 179 | | return new Result<SnapPoint>( |
| | 2 | 180 | | FormattableString.Invariant($"Could not snap to location: {location.longitude},{location.latitude}")); |
| | 110 | 181 | | } |
| | | 182 | | |
| | | 183 | | /// <summary> |
| | | 184 | | /// Iterative MaxDistance schedule: start at 50 m, ×4 per step, cap the |
| | | 185 | | /// growth at 10 km (so an unbounded MaxDistance doesn't produce an |
| | | 186 | | /// unbounded schedule), and always end with <paramref name="maxDistance"/> |
| | | 187 | | /// as the final entry. See snap-iterative-cutoff.md for the design. |
| | | 188 | | /// |
| | | 189 | | /// Examples: |
| | | 190 | | /// maxDistance = ∞ → 50, 200, 800, 3200, 12800, ∞ |
| | | 191 | | /// maxDistance = 1 000 → 50, 200, 800, 1000 |
| | | 192 | | /// maxDistance = 100 → 50, 100 |
| | | 193 | | /// maxDistance = 30 → 30 (single iteration, no growth) |
| | | 194 | | /// </summary> |
| | | 195 | | private static IEnumerable<double> ExpandSchedule(double maxDistance) |
| | 114 | 196 | | { |
| | | 197 | | const double start = 50.0; |
| | | 198 | | const double growthFactor = 4.0; |
| | | 199 | | const double growthCap = 10_000.0; |
| | | 200 | | |
| | 114 | 201 | | if (maxDistance <= start) |
| | 1 | 202 | | { |
| | 1 | 203 | | yield return maxDistance; |
| | 1 | 204 | | yield break; |
| | | 205 | | } |
| | | 206 | | |
| | 113 | 207 | | var d = start; |
| | 113 | 208 | | yield return d; |
| | 16 | 209 | | while (d < maxDistance && d < growthCap) |
| | 9 | 210 | | { |
| | 9 | 211 | | d *= growthFactor; |
| | 11 | 212 | | if (d < maxDistance) yield return d; |
| | 8 | 213 | | } |
| | 7 | 214 | | yield return maxDistance; |
| | 7 | 215 | | } |
| | | 216 | | |
| | | 217 | | /// <inheritdoc/> |
| | | 218 | | public async IAsyncEnumerable<SnapPoint> ToAllAsync(double longitude, double latitude, [EnumeratorCancellation] Canc |
| | 2108 | 219 | | { |
| | | 220 | | // calculate one box for all locations. |
| | 2108 | 221 | | (double longitude, double latitude, float? e) location = (longitude, latitude, null); |
| | 2108 | 222 | | var box = location.BoxAround(_offsetInMeter); |
| | | 223 | | |
| | | 224 | | // make sure data is loaded. |
| | 2108 | 225 | | await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken); |
| | | 226 | | |
| | | 227 | | // snap all. |
| | 2108 | 228 | | var snapped = _routingNetwork.SnapAllInBoxAsync(box, this, maxDistance: _maxDistance, cancellationToken: cancell |
| | 69590 | 229 | | await foreach (var snapPoint in snapped) |
| | 31633 | 230 | | { |
| | 31633 | 231 | | yield return snapPoint; |
| | 31633 | 232 | | } |
| | 2108 | 233 | | } |
| | | 234 | | |
| | | 235 | | /// <inheritdoc/> |
| | | 236 | | public async Task<Result<VertexId>> ToVertexAsync(double longitude, double latitude, CancellationToken cancellationT |
| | 1 | 237 | | { |
| | 1 | 238 | | (double longitude, double latitude, float? e) location = (longitude, latitude, null); |
| | | 239 | | |
| | | 240 | | // calculate one box for all locations. |
| | 1 | 241 | | var box = location.BoxAround(_maxDistance); |
| | | 242 | | |
| | | 243 | | // make sure data is loaded. |
| | 1 | 244 | | await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken); |
| | | 245 | | |
| | | 246 | | // snap to closest vertex. |
| | 1 | 247 | | var vertex = await _routingNetwork.SnapToVertexInBoxAsync(box, _costFunctions.Length > 0 ? this : null, maxDista |
| | 1 | 248 | | if (vertex.IsEmpty()) return new Result<VertexId>("No vertex in range found"); |
| | | 249 | | |
| | 1 | 250 | | return vertex; |
| | 1 | 251 | | } |
| | | 252 | | |
| | | 253 | | /// <inheritdoc/> |
| | | 254 | | public async IAsyncEnumerable<VertexId> ToAllVerticesAsync(double longitude, double latitude, |
| | | 255 | | [EnumeratorCancellation] CancellationToken cancellationToken = default) |
| | 0 | 256 | | { |
| | 0 | 257 | | (double longitude, double latitude, float? e) location = (longitude, latitude, null); |
| | | 258 | | |
| | | 259 | | // calculate one box for all locations. |
| | 0 | 260 | | var box = location.BoxAround(_maxDistance); |
| | | 261 | | |
| | | 262 | | // make sure data is loaded. |
| | 0 | 263 | | await _routingNetwork.UsageNotifier.NotifyBox(_routingNetwork, box, cancellationToken); |
| | | 264 | | |
| | | 265 | | // snap to closest vertex. |
| | 0 | 266 | | await foreach (var vertex in _routingNetwork.SnapToAllVerticesInBoxAsync(box, this, |
| | 0 | 267 | | maxDistance: _maxDistance, cancellationToken: cancellationToken)) |
| | 0 | 268 | | { |
| | 0 | 269 | | yield return vertex; |
| | 0 | 270 | | } |
| | 0 | 271 | | } |
| | | 272 | | |
| | | 273 | | private bool? IsAcceptable(IEdgeEnumerator<RoutingNetwork> edgeEnumerator) |
| | 57752 | 274 | | { |
| | 57752 | 275 | | var hasProfiles = _costFunctions.Length > 0; |
| | 57800 | 276 | | if (!hasProfiles) return true; |
| | | 277 | | |
| | 57704 | 278 | | var allOk = true; |
| | 230802 | 279 | | for (var p = 0; p < _costFunctions.Length; p++) |
| | 57704 | 280 | | { |
| | 57704 | 281 | | var costFunction = _costFunctions[p]; |
| | | 282 | | |
| | | 283 | | // check if the edge can be used in either direction. |
| | | 284 | | // both directions need to be checked here because SnapAllInBoxAsync |
| | | 285 | | // deduplicates by EdgeId: a one-way edge first encountered from its |
| | | 286 | | // head vertex would be rejected if only the tail-to-head direction is checked. |
| | 57704 | 287 | | var costs = costFunction.Get(edgeEnumerator, true, []); |
| | 57704 | 288 | | var costsReverse = costFunction.Get(edgeEnumerator, false, []); |
| | | 289 | | |
| | | 290 | | // if edge is not accessible in either direction, skip it. |
| | 57704 | 291 | | if (!costs.canAccess && !costsReverse.canAccess) |
| | 25947 | 292 | | { |
| | 25947 | 293 | | allOk = false; |
| | 25947 | 294 | | continue; |
| | | 295 | | } |
| | | 296 | | |
| | | 297 | | // check if needed if the edge can be stopped on (in either direction). |
| | 31757 | 298 | | if (_checkCanStopOn) |
| | 31694 | 299 | | { |
| | 31694 | 300 | | if (!costs.canStop && !costsReverse.canStop) |
| | 0 | 301 | | { |
| | 0 | 302 | | allOk = false; |
| | 0 | 303 | | continue; |
| | | 304 | | } |
| | 31694 | 305 | | } |
| | | 306 | | |
| | | 307 | | // check if the edge is on an island. |
| | 31757 | 308 | | if (_checkConnectivity && _islands.Length > 0) |
| | 15 | 309 | | { |
| | 15 | 310 | | var tailTileId = edgeEnumerator.Forward ? edgeEnumerator.Tail.TileId : edgeEnumerator.Head.TileId; |
| | 15 | 311 | | var islands = _islands[p]; |
| | | 312 | | |
| | | 313 | | // fast path: if the tile is fully done, just check _islandEdges. |
| | 15 | 314 | | if (islands.GetTileDone(tailTileId)) |
| | 8 | 315 | | { |
| | 8 | 316 | | if (islands.IsEdgeOnIsland(edgeEnumerator.EdgeId)) |
| | 1 | 317 | | { |
| | 1 | 318 | | allOk = false; |
| | 1 | 319 | | continue; |
| | | 320 | | } |
| | | 321 | | // tile done + not in island set → not island. |
| | 7 | 322 | | } |
| | | 323 | | else |
| | 7 | 324 | | { |
| | | 325 | | // Tile not done — ask this request's own graph, which is the only |
| | | 326 | | // thing that can answer "not an island" for an unfinished tile. |
| | 7 | 327 | | var onIsland = this.IsEdgeOnIslandInRequest(p, edgeEnumerator.EdgeId); |
| | 7 | 328 | | if (onIsland == true) |
| | 0 | 329 | | { |
| | 0 | 330 | | allOk = false; |
| | 0 | 331 | | continue; |
| | | 332 | | } |
| | | 333 | | |
| | 7 | 334 | | if (onIsland == false) |
| | 0 | 335 | | { |
| | | 336 | | // confirmed not island. |
| | 0 | 337 | | } |
| | | 338 | | else |
| | 7 | 339 | | { |
| | | 340 | | // not yet resolved — return null to trigger async resolution. |
| | 7 | 341 | | return null; |
| | | 342 | | } |
| | 0 | 343 | | } |
| | 7 | 344 | | } |
| | | 345 | | |
| | | 346 | | // any profile is good for a positive result. |
| | 31749 | 347 | | if (_anyProfile) return true; |
| | 31749 | 348 | | } |
| | | 349 | | |
| | 57697 | 350 | | return allOk; |
| | 57752 | 351 | | } |
| | | 352 | | |
| | | 353 | | bool? IEdgeChecker.IsAcceptable(IEdgeEnumerator<RoutingNetwork> edgeEnumerator) |
| | 57752 | 354 | | { |
| | 57752 | 355 | | return this.IsAcceptable(edgeEnumerator); |
| | 57752 | 356 | | } |
| | | 357 | | |
| | | 358 | | /// <summary> |
| | | 359 | | /// Island verdict from state this request owns: the durable set says island, this |
| | | 360 | | /// request's graph says not-island, otherwise unknown and the caller resolves. |
| | | 361 | | /// </summary> |
| | | 362 | | private bool? IsEdgeOnIslandInRequest(int profileIndex, EdgeId edgeId) |
| | 7 | 363 | | { |
| | 7 | 364 | | if (_islands[profileIndex].IsEdgeOnIsland(edgeId)) return true; |
| | | 365 | | |
| | | 366 | | // No graph yet means nothing has been classified in this request, |
| | | 367 | | // do not create one just to ask. |
| | 7 | 368 | | var dg = _islandDgFull[profileIndex]; |
| | 7 | 369 | | if (dg != null && dg.IsNotIsland(edgeId)) return false; |
| | | 370 | | |
| | 7 | 371 | | return null; |
| | 7 | 372 | | } |
| | | 373 | | |
| | | 374 | | async Task<bool> IEdgeChecker.RunCheckAsync(IEdgeEnumerator<RoutingNetwork> edgeEnumerator, CancellationToken cancel |
| | 7 | 375 | | { |
| | | 376 | | // Nothing to resolve: without a connectivity question IsAcceptable never returns null, |
| | | 377 | | // so arriving here at all means the answer is already in. |
| | 7 | 378 | | if (!_checkConnectivity) return (this as IEdgeChecker).IsAcceptable(edgeEnumerator) ?? true; |
| | | 379 | | |
| | | 380 | | // Build the edge's tile first so every traversable edge in the tile |
| | | 381 | | // gets a definitive Island / NotIsland verdict via ClassifyAsync. |
| | | 382 | | // Subsequent snap candidates in the same tile then short-circuit on |
| | | 383 | | // the per-profile Islands set / dg fast-paths. The IslandManager |
| | | 384 | | // deduplicates concurrent builds for the same (profile, tile). |
| | 7 | 385 | | var tailTileId = edgeEnumerator.Forward ? edgeEnumerator.Tail.TileId : edgeEnumerator.Head.TileId; |
| | 24 | 386 | | for (var p = 0; p < _profiles.Length; p++) |
| | 7 | 387 | | { |
| | 7 | 388 | | var profile = _profiles[p]; |
| | 7 | 389 | | await _routingNetwork.IslandManager.BuildForTileAsync(_routingNetwork, profile, tailTileId, |
| | 7 | 390 | | _islandDgFull[p] ??= new IslandDirectedGraph(), |
| | 7 | 391 | | _islandDgNonLocal[p] ??= new IslandDirectedGraph(), cancellationToken); |
| | 7 | 392 | | if (cancellationToken.IsCancellationRequested) return true; |
| | | 393 | | |
| | 7 | 394 | | var islands = _routingNetwork.IslandManager.GetIslandsFor(profile); |
| | 9 | 395 | | if (islands.IsEdgeOnIsland(edgeEnumerator.EdgeId)) return false; |
| | | 396 | | // tile DONE + not in Islands set → NotIsland → acceptable for this profile. |
| | 5 | 397 | | } |
| | | 398 | | |
| | 5 | 399 | | return (this as IEdgeChecker).IsAcceptable(edgeEnumerator) ?? true; |
| | 7 | 400 | | } |
| | | 401 | | } |