Overview
The aim of this process is to take the five walks and break them down into segments where each segments represents part of a walk where one or more of the routes is common to that segment. We’ll step through he process using an Alnmouth walk as an example because it is the simplest from this point of view consisting of a coastal walk with each lower level walk joining the route of walk 1 at intervals near the destination.
Segments
Each walk is can consist of one or more segments. Each segments can contain either an array of waypoints or an array of nested segments. It can never have both.
The process is all about taking the starting segment, an array of points, and breaking down into a sequence of parts corresponding to where the route is shared by one or more of the other walks.
Walk 1 & 2
We start with the top walks, walk one and compare it with the next walk down walk two.
We take each point on seg-1 and compare it with all of the points on seg-2 looking for a match. Once a match is found, we look along both walks to see if the overlap continues and when it does, we can create new segments.
The mechanism for matching the points on the segments will described in detail later.
Once the overlap in the routes has been determined, both of these walks are then split into three.
- The section before they meet the common section. may not exist
- The common part of the routes that’s present in both routes
- The part of the route after. may not exist
In many cases the section before and after the overlap may not exist (zero length) or be too short to be worth bothering with, in which case it gets folded into the common section for that segment. This usually happens when walks share a start or finish and the precise position of that point varies too much.
This is the result from the Alnmouth walk
In both cases, in the original segment, the array of points is replaced by an array of segments. In the lower walk the overlap section is replace by a copy of the one from the upper walk. A copy of the original is kept with the them having previously and replacedBy pointers referring to each other. Neither is used the any further searches and are only retained in case needed for investigation and to produce explanatory displays such as on this page.
Walk 1 & 3
The next step is to take the walk 1 and compare it with the next walk down, walk 3, and look for overlaps.
Walk 1 now consists of two segments, seg-1b and seg-12, so we take each of those segments in turn and compare it with the current single segment of walk 3, seg-3.
When each segment is created we also determine the coordinates of the bounding rectangle containing that segment, and a quick check of the rectangles for seg-1b and seg-3 shows that they don’t overlap and so we reject comparing them without looking at the individual waypoints.
If we are comparing two segment of 100 points each then we would have up to 10,000 point comparisons looking for a match. If, as well as the bounding rectangle for the whole segment, we created an array of bounding rectangles for every 10 points, then we would only need 100 comparison of the bounding rectangle ( a much cheaper operation) and then only up to 100 comparisons of actual points when the rectangles overlap.
A variation would be to do a binary search. i.e. calculate the bounding rectangles for half the segments on the fly and compare them. If Overlapping, then do the same again with those subset of points until the resulting set of points are sufficiently small.
So far performance has been fine and optimisations along these lines has not been attempted.
An overlap is found between the second segment seg-12 and seg-3 so again we split both walks to create new segments.
Walk 1 & 4
We do the same for walk 4
Walk 1 & 5
and finally for walk 5
The net result is the walk 1 has gone from a single segment listing a series of waypoints to a nested tree of segment as shown in the image below where only the grey squares are segments containing actual waypoints
Walk 2 & 3 etc.
The next step is to iterate doing the same for the lower walks. i.e.
- compare the current segments of walk 2, with those of walks 3,4 and 5, ignoring any segments involving walk 1.
- compare the current segments of walk 3, with those of walks 4 and 5, ignoring any segments involving walk 1 & 2.
- compare the current segments of walk 4, with those of walks 5, ignoring any segments involving walk 1,2 & 3.
With this particular walk that resulted in no new segmentation.
The resulting Segments
The extracting the resulting unique segments give us the data we were after.
The Map
And this is used to produce the display
