My Route Reducution Algorithm
To reduce a route 'X' to a new route 'Y' with a smaller
number of points the basic algorithm is as follows:
-
Mark all points in route 'X' as 'not included' except
the first and last points.
-
Find an unincluded point in route 'X' that if marked as included
will retain the shape of the entire route as much as possible, then mark
it as included.
-
Repeat step 2 until you have as many points marked as included as you
want to have in route 'Y'.
-
Take each point marked as included from route 'X' and add them
in sequence to route 'Y'.
The above algorithm will produce a reduced route but step 2 is the
crucial step in retaining the shape of route 'A' and is now
described in detail by an example run-through of the algorithm.
Fig. 1
In the diagram (fig. 1), red dots represent points that have already
been included, gray dots represent points that have not yet been
included. Notice that only the start and end points are included at this
time.
The aim at this stage is to find an unincluded point which would add
the greatest distance to the total length of the route if it
were to be included. The distance that a point adds to a route is
calculated as follows:
Fig. 2
-
Take the two included points (A and B) on either side of the point in
question (C) so that if by traversing the points in sequence between A
and B no other included points are passed.
-
Measure the Great-Circle distance between A and B, call this distance
|AB|.
-
Measure the Great-Circle distance between A and C, call this distance
|AC|.
-
Measure the Great-Circle distance between C and B, call this distance
|CB|.
The distance that C would add to the length of the route if it were to
be included is equal to:
|AC| + |CB| - |AB|.
Let us say in this example that the point C
does add the
greatest distance to the route and was therefore included. Now we wish to
also include a fourth point.
Fig. 3
Consider the points D and E (although in reality we would consider each
and every point between A and C and between C and B). Suppose that we
have found that of the points between A and C, D adds the greatest
distance, and that of the points between C and B, E adds the greatest
distance. We must now compare the distances that D and E add to the route
length. We find that E adds the greatest distance and it is therefore
included. This results in the route (fig. 4).
Fig. 4
Figure 4 shows the reduced route, and it does retain much of the shape of
the original route. However, if a point is important to be retained, e.g.
a point on the route which represents an important stopping point, then
the route-reduction algorithm can take this into account if you mark the
important points as included (as well as the start and end points) before
the algorithm is applied.
Fig. 5
Figure 5 shows an original route (around 1000 points) in blue and the
reduced route (50 points) in red.
