Skip router

This router tries to find the farthest route with the underlying Backtrack router. If beneficial, specific sampling points are requested to be ignored by the underlying routers.

Each time the underlying router has found its farthest route and this route does not reach the sampling point Goal, the probability is high that some of the last sampling points’s track positions were recorded with an inaccurate GPS source or due to street map errors. The router therefore starts to skip consecutive sampling points in a specific, skip-distance-dependant order, starting with the last sampling point of the farthest route or the following. The underlying routers then try to route farther by ignoring these sampling points.

If it is able to route farther, the skipping is considered successful and it continues as usual. It then may start a new skipping session, if necessary.

If the distance to skip reaches some threshold before finding a route, the router returns the route before the last skipping session has begun.

Example

In this example, the underlying router failed to route beyond sampling point 4, as shown below.

Farthest route does not reach Goal

Fig. 31 Farthest route does not reach Goal

The router now starts skipping sampling points consecutively from both directions until it is able to find a route.

To decide whether it should skip over a sampling point from behind or from ahead, it calculates the linear distances that need to be skipped (from sampling point to sampling point) and chooses the option where this is minimal.

Note

Depending on the chosen strategy (samplingPointSkipStrategy), the distances are measured from the sampling points before/after the to-be-skipped sampling points (includeEdgeCosts) or from the outermost sampling points that are to be skipped (excludeEdgeCosts). In the latter case the costs are zero for the first trial; as a rule the sampling point ahead is choosen to be skipped first.

Note

The selection process tries out three different consecutively growing sampling point selections in parallel and always chooses the next with the minimal distance to be skipped:

  1. The first growing selection consists of the sampling point ahead and the following.

  2. The second growing selection consists of the sampling point before and the preceeding.

  3. The third selection can grow in both directions, depending on which next sampling point to skip has the minimal distance to the one before.

For simplicity, we now focus on the strategy includeEdgeCosts and assume that only the third growing selection process is used (growing to both directions).

This selection process is illustrated in Fig. 32.

Note

The distance is always measured as a linear distance, beginning at one of the first two sampling points causing the router to start the skipping process (in our example 4 and 5). It is calculated using the haversine formula.

Choosing sampling point to skip

Fig. 32 Choosing sampling point to skip

In our example the router choosed to skip sampling point 4.

Now the routing continues, but the underlying router still does not find a route to go on. So the selection process is repeated, as shown in Fig. 33.

Skipped sampling point 4

Fig. 33 Skipped sampling point 4

Now sampling points 4 and 5 are requested to be skipped.

Again, the underlying router failes to find a route and selection process is repeated, as shown in Fig. 34.

Disallowed skip (D)

Fig. 34 Skipped sampling points 4 and 5

Now sampling points 3 to 5 are requested to be skipped.

Finally, the routing proceeds, illustrated in Fig. 35.

Routed farther by skipping 3 sampling points

Fig. 35 Routed farther by skipping 3 sampling points

Sampling points 3, 4 and 5 are ignored now. However, the route is still consecutive.