Implementing Douglas-Peucker In PHP: Part 1

Implementing Douglas-Peucker In PHP: Part 1

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

Listing 1 The ShapePoint class, used to represent a single point in a shape (ShapePoint.php)

<?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)

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