Reducing a Map Path Using Douglas-Peucker Algorithm

By Quentin Zervaas, 27 April 2011 KML Maps PHP Download PDF

Introduction

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.

Figure 1 A GTFS shape containing 400 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.