Reducing a Map Path Using Douglas-Peucker Algorithm

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.

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.

Figure 2 A GTFS shape reduced from 400 to 70 points

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.

• Next: The Douglas-Peucker Algorithm

Additional Files

• shapes.txt
  (19KB)