Reducing a Map Path Using Douglas-Peucker Algorithm


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.

Note: The format of this data isn’t overly important. You can read all about it in the GTFS spec. The important part is that each point has a latitude and longitude, and the order of points is defined.

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 A and B respectively). 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 X).
  • Repeat this algorithm twice: once using A as the first point and X as the last point, the other time using X as the first point and B as 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:

  1. 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
  2. Shape: An instance of this represents a shape that we want to reduce. It consists of a series of ShapePoint objects
  3. 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 seq).

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 (points()).

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 points() function.

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 ShapeReducer class.


The final class we need to implement is the ShapeReducer class.

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:

  1. The entry point for the reducer
  2. The recursive function
  3. 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 ShapeReducer class.

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_lat and 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 shape_pt_sequence).

Note: If you were parsing a full shapes.txt file from a GTFS feed you would need to appropriately handle all columns

Using PHP’s fgetcsv() function, we can parse this file and build a Shape using the code in Listing 5.

The code in Listing 6 shows how to output the shape using the Google Maps API. If you’re interested in how the Google Maps JavaScript API works, you can refer to the documentation.

This code works by outputting all of the points in the shape into a JavaScript API, then using those points to build a polyline in Google Maps. Additionally, this code determines the bounding box around the points in the shape so we automatically zoom in on the line.

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.

Further Reading



Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedIn

3 thoughts on “Reducing a Map Path Using Douglas-Peucker Algorithm

  1. I knew someone would have already solved the too many points on a GTFS map challenge. Thanks to your article we don’t need to “reinvent this wheel”.

Leave a Reply

Your email address will not be published. Required fields are marked *