PhpRiot
Become Zend Certified

Prepare for the ZCE exam using our quizzes (web or iPad/iPhone). More info...


When you're ready get 7.5% off your exam voucher using voucher CJQNOV23 at the Zend Store

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.

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

In This Article


Additional Files