With these preliminaries, we can now describe the algorithm for generating the levels string. We first prescribe a small error tolerance - distances smaller than this error tolerance will essentially be ignored. This is the parameter verySmall in the form. We start by encoding the endpoints with a "P", since we certainly would like these to appear. Call these endpoints A and B. We then scan the list of points in the path and find the one farthest away from the line segment [A,B], call it C. If the distance from C to [A,B] is less than verySmall, then we are done and our polyline approximation will be a single line segment. Otherwise, label the point C with it's distance to [A,B] and call the procedure recursively on the portion of the line between A and C and the portion of the line between C and B. This procedure will eventually terminate.
Now each point on the line is either labeled with a distance from a sub-segment of the line or it is unlabeled. The unlabeled points will be discarded. The labeled points will be encoded according to the size of their label. More precisely, the point will appear at and after zoom level n for the polyline if:
Finally, we can refer to the list in the previous section to determine the character to encode the point with. Note that the larger the label, the sooner the point appears as we zoom into the line.
As an example, consider the path of 360 points shown below. This is actual data collected from my GPS and exhibits some characteristics common to GPS data. Reception was great in town so we have many data points where the streets are straight. As the path moves into hillier terrain, it becomes very curvy. The path then moves into a heavily wooded area, resulting in fewer data points.
The encoding algorithm begins by encoding the endpoints with a "P". These endpoints determine a line segment, which could be considered to be a zeroth level approximation.
To step to the first level approximation, we find the point on the path whose distance from the zeroth level approximating segment is the greatest. In this case, that distance works out to be 0.0099.
This point will be encoded with an "H" because
and "H" is the ninth character in our sequence of encodings. Since it's
just the 9 we're interested in, we can compute it as
Math.floor(Math.log(0.0099/0.00001)/Math.log(2)).
The following animation illustrates the first few steps of the process.
The algorithm just described is essentially a minor extension of the Douglas-Peucker algorithm for polyline simplification. The Douglas-Peucker algorithm is an important algorithm in computational cartography and is described at this webpage. Incidentally, my old algorithm was essentially an extension of the vertex reduction algorithm described at that same webpage.