This post has already been read 4665 times!

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.

e448-58-600--9cc6

92f3-59-600--849e

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

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.

a4fe-60-600--95ea

Implementing Douglas-Peucker In PHP: Part 1

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 ShapePoint objects
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).

Listing 1 The ShapePoint class, used to represent a single point in a shape (ShapePoint.php)
    class ShapePoint
    {
        public $lat;
        public $lng;
        public $seq;
 
        public function __construct($lat, $lng, $seq)
        {
            $this->seq = $seq;
            $this->lat = $lat;
            $this->lng = $lng;
        }
    }

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.

Listing 2 The Shape class, used to represent a shape that can be reduced (Shape.php)

    require_once('ShapePoint.php');
 
    class Shape
    {
        /**
         * @var ShapePoint[]    The list of points in the shape
         */
        protected $_points = array();
 
        /**
         * @var bool    Whether or not the list of points needs sorting
         */
        protected $_needsSort = false;
 
        /**
         * Add a point to the shape. Marks the list of points as out-of-order
         *
         * @param   ShapePoint  $point  The point to add to the shape
         */
        public function addPoint(ShapePoint $point)
        {
            $this->_points[] = $point;
            $this->_needsSort = true;
            return $this;
        }
 
        /**
         * Get the list of points. If the list is out of order
         * it is sorted by sequence value prior to returning
         *
         * @return  ShapePoint[]
         */
        public function points()
        {
            if ($this->_needsSort) {
                usort($this->_points, array(__CLASS__, 'sort'));
                $this->_needsSort = false;
            }
 
            return $this->_points;
        }
 
        /**
         * Sort callback to sort ShapePoint by sequence
         *
         * @param   ShapePoint  $a
         * @param   ShapePoint  $b
         * @return  int         -1, 0, or 1
         */
        public static function sort($a, $b)
        {
            if ($a->seq < $b->seq) { return -1; }
            if ($a->seq > $b->seq) { return 1; }
            return 0;
        }
    }

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:

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 ShapeReducer class.
Listing 3 The ShapeReducer class, used to reduce the number of points in a shape (ShapeReducer.php)

    class ShapeReducer
    {
        /**
         * Reduce the number of points in a shape using the Douglas-Peucker algorithm
         *
         * @param   Shape   $shape      The shape to reduce
         * @param   float   $tolerance  The tolerance to decide whether or not
         *                              to keep a point, in geographic
         *                              coordinate system degrees
         * @return  Shape   The reduced shape
         */
        public function reduceWithTolerance($shape, $tolerance)
        {
            // if a shape has 2 or less points it cannot be reduced
            if ($tolerance <= 0 || count($shape->points()) < 3) {
                return $shape;
            }
 
            $points = $shape->points();
            $newShape = new Shape(); // the new shape to return
 
            // automatically add the first and last point to the returned shape
            $newShape->addPoint($points[0]);
            $newShape->addPoint($points[count($points) - 1]);
 
            // the first and last points in the original shape are
            // used as the entry point to the algorithm.
            $this->douglasPeuckerReduction(
                $shape,             // original shape
                $newShape,          // reduced shape
                $tolerance,         // tolerance
                0,                  // index of first point
                count($points) - 1  // index of last point
            );
 
            // all done, return the reduced shape
            return $newShape;
        }
 
        /**
         * Reduce the points in $shape between the specified first and last
         * index. Add the shapes to keep to $newShape
         *
         * @param   Shape   $shape      The original shape
         * @param   Shape   $newShape   The reduced (output) shape
         * @param   float   $tolerance  The tolerance to determine if a point is kept
         * @param   int     $firstIdx   The index in original shape's point of
         *                              the starting point for this line segment
         * @param   int     $lastIdx    The index in original shape's point of
         *                              the ending point for this line segment
         */
        public function douglasPeuckerReduction(Shape $shape, Shape $newShape, $tolerance, $firstIdx, $lastIdx)
        {
            if ($lastIdx <= $firstIdx + 1) {
                // overlapping indexes, just return
                return;
            }
 
            // retrieve all points for subsequent processing
            $points = $shape->points();
 
            // loop over the points between the first and last points
            // and find the point that is the furthest away
 
            $maxDistance = 0.0;
            $indexFarthest = 0;
 
            $firstPoint = $points[$firstIdx];
            $lastPoint = $points[$lastIdx];
 
            for ($idx = $firstIdx + 1; $idx < $lastIdx; $idx++) {
                $point = $points[$idx];
 
                $distance = $this->orthogonalDistance($point, $firstPoint, $lastPoint);
 
                // only keep the point with the greatest distance
                if ($distance > $maxDistance) {
                    $maxDistance = $distance;
                    $indexFarthest = $idx;
                }
            }
 
            // if the point that is furthest away is within the tolerance,
            // it is simply discarded. Otherwise, it's added to the reduced
            // shape and the algorithm continues
            if ($maxDistance > $tolerance) {
                $newShape->addPoint($points[$indexFarthest]);
 
                // reduce the shape between the starting point to newly found point
                $this->douglasPeuckerReduction($shape, $newShape, $tolerance, $firstIdx, $indexFarthest);
 
                // reduce the shape between the newly found point and the finishing point
                $this->douglasPeuckerReduction($shape, $newShape, $tolerance, $indexFarthest, $lastIdx);
            }
        }
 
        /**
         * Calculate the orthogonal distance from the line joining the
         * $lineStart and $lineEnd points from $point
         *
         * @param   ShapePoint  $point      The point the distance is being calculated for
         * @param   ShapePoint  $lineStart  The point that starts the line
         * @param   ShapePoint  $lineEnd    The point that ends the line
         * @return  float   The distance in geographic coordinate system degrees
         */
        public function orthogonalDistance($point, $lineStart, $lineEnd)
        {
            $area = abs(
                (
                    $lineStart->lat * $lineEnd->lng
                  + $lineEnd->lat * $point->lng
                  + $point->lat * $lineStart->lng
                  - $lineEnd->lat * $lineStart->lng
                  - $point->lat * $lineEnd->lng
                  - $lineStart->lat * $point->lng
                ) / 2
            );
 
            $bottom = sqrt(pow($lineStart->lat - $lineEnd->lat, 2) + pow($lineStart->lng - $lineEnd->lng, 2));
 
            return $area / $bottom * 2.0;
        }
    }

In the next section I'll show you how to use the three PHP classes we've just created.

A Working Example Using Google Maps

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.
Listing 4 A sample of the GTFS shapes.txt file (shapes.txt)

shape_id,shape_pt_lat,shape_pt_lon,shape_pt_sequence,shape_dist_traveled
27779,-33.3240789844364,115.638325287067,1,0
27779,-33.3240755555556,115.638360555556,2,3.31
27779,-33.3240722222222,115.638396666667,3,6.69
27779,-33.3240783333333,115.638419444444,4,8.91

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.
Listing 5 Code to parse the shapes.txt and create a new shape (listing-5.php)

    require_once('Shape.php');
 
    $fp = fopen('shapes.txt', 'r');
 
    $shape = new Shape();
 
    $i = 0;
    while (($row = fgetcsv($fp))) {
        if ($i == 0) {
            // csv header row
        }
        else {
            $shape->addPoint(
                new ShapePoint($row[1], $row[2], $i)
            );
        }
 
        $i++;
    }
 
    fclose($fp);

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.
Listing 6 Displaying a shape on a map using Google Maps (listing-6.php)





Points: echo count($shape->points())


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.
Listing 7 Reducing a shape with ShapeReducer (listing-7.php)

    require_once('ShapeReducer.php');
    $reducer = new ShapeReducer();
    $shape = $reducer->reduceWithTolerance($shape, 0.00005);

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.
Listing 8 Displaying a reduced shape on a map using Google Maps (listing-8.php)

    require_once('Shape.php');
 
    $fp = fopen('shapes.txt', 'r');
 
    $shape = new Shape();
 
    $i = 0;
    while (($row = fgetcsv($fp))) {
        if ($i == 0) {
            // csv header row
        }
        else {
            $shape->addPoint(
                new ShapePoint($row[1], $row[2], $i)
            );
        }
 
        $i++;
    }
 
    fclose($fp);
 
    require_once('ShapeReducer.php');
    $reducer = new ShapeReducer();
    $shape = $reducer->reduceWithTolerance($shape, 0.00005);


    
        
        
        
    
    
        Points: points()) ?>
        

As you can see, we've managed to reduce 400 points to 70, without a significant loss in quality of the line.

Summary

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

Douglas-Peucker algorithm on Wikipedia
Google Maps JavaScript API

Comments are closed.

Post Navigation