Finding the Route Overlap

We now have a start point, on SegB that lies on (i.e. close enough) to SegA.

The next task is to figure the extent to which the two segments now follow a common route. A number of different approaches have been tried before alighting on this one which is the cleanest and, I hope, easiest to describe.

The basic approach is to enter a loop advance along the points of segA and/or SegB checking that they lie on each others route and stopping when they come to an end or diverge. The most difficult problem has been to handle the fact that along any part of the path one segment could have a lot more waypoints than on the other segment.

Indices

Our position on the two segment is determined by the indexes iA and iB which indicate the points ptA1 and A1 which are the latest points on each route that lie on the common segment. We need to consider the next two points, ptA2 and ptB2 and determine if and how they contribute to the continuation of the common segment.

Basic Options

There are 4 basic cases that can occur

1. ptA2 and ptB2 are close enough to each other to be the new latest point. We can increment iA and iB and they become the new current points.
2. ptB2 lies on the leg of segA between ptA1 and ptA2. We can increment iB to progress along segB.
3. ptA2 lies on the leg of segB between ptB1 and ptB2. We can increment iA to progress along segA.
4. None of the above apply in which case the walks are diverging and the current points are the end of the common section.

Calls to distToLeg(ptA1, ptA2, ptB2) provides the data to resolve the first two case and distToLeg(ptB1, ptB2, ptA2) resolves the third. If neither returns isNearToLine then we have the fourth case.

An Example

This perhaps becomes clear by considering an example.

distToLeg(ptA1, ptA2, ptB2) "returns"  {isOnLine: false,  matchP2: false, ...}
distToLeg(ptB1, ptB2, ptA2) "returns"  {isOnLine: true,  matchP2: false, ...}

iA++; // move along segA

distToLeg(ptA1, ptA2, ptB2) "returns"  {isOnLine: false, matchP2: false, ...}
distToLeg(ptB1, ptB2, ptA2) "returns"  {isOnLine: true, matchP2: false, ...}

iA++; // move along segA

distToLeg(ptA1, ptA2, ptB2) "returns"  {isOnLine: true, matchP2: false, ...}
distToLeg(ptB1, ptB2, ptA2) "returns"  {isOnLine: false, matchP2: false, ...}

iB += step; // move along segB

distToLeg(ptA1, ptA2, ptB2) "returns"  {isOnLine: true, matchP2: true, ...}
distToLeg(ptB1, ptB2, ptA2) "returns"  {isOnLine: true, matchP2: true, ...}

iB += step; // move along segB
iA += 1;    // move along segA

if (!ptA2) break; // end of segA reached
if (!ptB2) break; // end of segB reached
distToLeg(ptA1, ptA2, ptB2) "returns" B= {isNearLine: false, ...}
distToLeg(ptB1, ptB2, ptA2) "returns" A= {isNearLine: false, ...}
if (!A.isNearLine && !B.isNearline)break; // the lines diverge

isOnLine v isNearLine

Sometimes the encoding of the walk drifts out a little and the points in a long run aren’t as close as we would like. Allowing extra leeway means we don’t break into as many segments as we would otherwise but it does cause a little extra confusion that needs to be dealt with.

As described earlier we make two calls to distToLeg

(A) distToLeg(ptA1, ptA2, ptB2)
(B) distToLeg(ptB1, ptB2, ptA2)

Both can return isOnLine, isNearLine, or nothing in order of preference. It uses the data from the two call in the following order of priority

• (A).isOnLine use (A)
• (B).isOnLine use (B)
• (A).isNearLine and (B).isNearLine then use the one returning the minimum distance.
• Only one returning isNearLine then use that one.
• Neither are acceptable - End of common section.

The use of points that are only near to, rather than close to, the line is only acceptable in the middle of the overlap. At the end of the common section, any such points after the last isOnLine point, are deemed to be part of the diverging of the routes and are not included in the overlap.

Reverse Routes

Just as with the finding the start of the overlap, we have to contend with the issue of the segB walking in the opposite direction to segA.

This is handled by having a loop where step is tried with values +1* amd -1.
The explanation above talked in terms of incrementing iB but in practice this is iB+step.
It looks for an overlap in the same direction as segA i.e. step = +1 and if that doesn’t work it iterates around and tries the reverse direction. step = -1.

Ignoring Small Overlaps

Before finally splitting the segments. The length of the overlap is calculated and if it’s small, currently less than 100m, we bail out and ignore it.

The two instance from a Grasmere walk shows that preserving with these overlaps would not have added any clarity and would only increase the complexity.

Getting it wrong

If we get the precise location where one segment transitions into another wrong, it isn’t usually serious and isn’t noticeable unless we zoom in closely.

The images below illustrate a typical problem.