When drawing a path on a map (for instance, the directions from point A to point B) it is important to consider the limitations of the device you’re drawing the path on.
In this article, I will show you how to reduce the number of points in a path so the path can be displayed with minimal loss of quality on devices such as iPhone or Android-powered devices that may struggle with an extremely large set of points.
A Real-World Example: General Transit Feed Specification (GTFS)
In recent times I’ve been developing an iOS application called TransitTimes. This application uses publicly-available GTFS (General Transit Feed Specification) data to provide users with offline public transit timetables.
Part of the GTFS specification is the shapes.txt file. This is a CSV (comma-separated values) file that describes any number of shapes used in the public transit data. Each row in this file corresponds to a single point in a single shape.
For the examples in this article, I’ve extracted a shape from Transperth’s GTFS feed.
When rendered in Google Maps (the code to do so is included later in this article), the path looks as in figure 1. This path is made up of 400 separate points.
Using the technique described in this article, we can reduce the number of points to around 70 without any significant loss of quality. This is demonstrated in figure 2.
In the next section, I’ll introduce you to the Douglas-Peucker algorithm. This is the algorithm used in the example just given to reduce 400 points to 70.
The Douglas-Peucker algorithm is used to reduce the number of points in a line. It does so by discarding points that do not deviate significantly between its surrounding points.
The amount a point may deviate before it is excluded is an input to the algorithm, and naturally will impact the number of points that are excluded.
The algorithm works as follows:
- Begin with the first and last points in the path (let’s call them
Brespectively). These are always kept.
- Find the point between the first and last that is furthest away from the line joining the first and last line (the orthogonal distance).
- If this point is greater than the allowed tolerance, this point is kept (let’s called it
- Repeat this algorithm twice: once using
Aas the first point and
Xas the last point, the other time using
Xas the first point and
Bas the last point.
This algorithm is recursive, and continues until all points have been checked.
In the next section we’ll implement the Douglas-Peucker algorithm in PHP.
To implement the Douglas-Peucker algorithm in PHP, we’re going to create 3 separate PHP classes:
ShapePoint: An instance of this represents a single point in a shape. It consists of a coordinate and a value to indicate its order in the shape
Shape: An instance of this represents a shape that we want to reduce. It consists of a series of
ShapeReducer: This is the class that implements the algorithm. It reduces a shape using a given tolerance and returns a new shape.
The ShapePoint Class
This class consists of a coordinate (the latitude and longitude), as well as a number to indicates its sequence in the shape (represented by
The Shape Class
This class is made up of a series of shape points (that is, instances of
ShapePoint). Additionally, it contains a method to retrieve all points that have been added (
When creating a reduced shape with the Douglas-Peucker algorithm, points are not necessarily added in the correct order that they should appear. This is the reason for tracking the sequence in
ShapePoint. This is also the reason we sort the array of points if required in the
Rather than sorting the shape every time a new point is added, we simply store a boolean that indicates the shape may be out of order. This way it’s only sorted on-demand, and it’s only sorted once (not every single time
points() is called).
To simplify matters, we leave it up to the creator of the points to set valid sequence values.
The entire code for
Shape is shown in Listing 2.
In the next section I’ll show you how the map reduction algorithm is implemented when we create the
The final class we need to implement is the
As mentioned earlier in this article, this algorithm is recursive (meaning it calls itself until complete), and we need to determine the orthogonal distance for a point from the (imaginary) line joining two other points.
Thus, we need to implement three methods:
- The entry point for the reducer
- The recursive function
- A function to determine orthogonal distance
Rather than breaking down every line of code, I’ve included a number of comments in the following listing, which shows the code for the
In the next section I’ll show you how to use the three PHP classes we’ve just created.
Earlier in this article we took a brief look at the
shapes.txt in the GTFS specification. We will now read data from this file and plot it on a map using the Google Maps API.
We will then reduce the shape using the
ShapeReducer class and plot the reduced shape on a map. This will demonstrate that the number of points in a shape can safely be reduced.
The data in
shapes.txt looks similar to that in Listing 4. The entire data file used in this example is available with this article.
To simplify matters, we’re only interested in
shape_pt_lon columns. We’re going to ignore the other 3 columns (we’ll assume the points are already in order, so we won’t worry about
shapes.txtfile from a GTFS feed you would need to appropriately handle all columns
fgetcsv() function, we can parse this file and build a
Shape using the code in Listing 5.
Changing this code to show a reduced shape now is extremely simple. Listing 7 shows the lines to add before outputting the HTML to reduce the shape.
The tolerance value is specified in degrees of latitude/longitude. The precise distance this corresponds to changes depending on the location on Earth, but you can experiment with this value to see the impact it has on the number of points in the reduced shape.
Listing 8 shows the entire code for parsing the shapes data, building the shape, reducing the shape, then outputting the shape on a map with Google Maps.
As you can see, we’ve managed to reduce 400 points to 70, without a significant loss in quality of the line.
In this article I showed you how to reduce the number of points in path or shape that is to be rendered on a map using the Douglas-Peucker algorithm.
The primary reason for doing so is because mobile devices have limited capacity, and may struggle to show lines that have an extremely large number of points when lower-quality representation of the line is sufficient.
To demonstrate this in action, I used the shapes data from a General Transit Feed Specification (GTFS) data file. In the example, we reduced a shape made up 400 points to 70 points and rendered both on a map using the Google Maps API. In both instances the shape looked the same, yet the shape using only 70 points can be rendered far more easily on a device with limited capabilities.
- Douglas-Peucker algorithm on Wikipedia
- General Transit Feed Specification