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 advance along the points of SegB and check that they lie on SegA. 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.

Our position on the two segment is determined by the indexes iA and iB. We need increment these as they move along the two paths until we reach a stage where one or other segment ends or they diverge.

In the chart above we currently have a common point at iA and iB and we need to find out if the next point on B is still on SegA. The approach is to use distToLeg to test iB+1 against a series of legs of SegA.

1. Test iB+1 against the leg between iA and iA+1
2. Maybe its on the next leg so test iB+1 against the leg between iA+1 and iA+2
3. sometimes the points don’t always go forward so could be on the previous leg? Test iB+1 against the leg between iA-1 and iA
4. Test iB+1 against the leg between iA+2 and iA+3
5. Test iB+1 against the leg between iA+3 and iA+4
6. Test iB+1 against the leg between iA+4 and iA+5

If any any of these report back as isOnLine then we stop going down the list adjust iA and iB appropriately and move on to the next point on B.

Any tests that report as isNearLine are compared and the one with the least dist selected and used to advance the search. The idea here is that if the encoding has been a bit lax and got a bit of range for a short stretch and we don’t want to create unnecessary multiple segments.

We have an array common that acts as a stack and as each point is accepted it’s data is pushed onto the stack

If all of the tests above fail then we assume the point is not even near segA and the two segments have diverged.

Backtracking

Now we need to firm up where the common section ends.

Now that we have them diverging we go into a loop looking at the last entry in common and pop it off the stack if it is only isNearLine. The end is the last point that we found that is isOnLine.

The end point has a type value, just like the start, with values AB, A or B.

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 looking at iB+1 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 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 persevering with these overlaps would not have added any clarity and would only increase the complexity.