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

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

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)

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

<html>
    <head>
        <script type="text/javascript" src="http://maps.google.com/maps/api/js?sensor=false"></script>
        <script type="text/javascript">
            function initialize() {
                var map = new google.maps.Map(
                    document.getElementById('map'),
                    { mapTypeId: google.maps.MapTypeId.ROADMAP }
                );
 
                var points = [
                    <?php foreach ($shape->points() as $k => $point) {  ?>
                        <?php if ($k > 0) {  ?>,<?php } ?>
                        new google.maps.LatLng(<?php echo $point->lat ?>, <?php echo $point->lng ?>)
                    <?php } ?>
                ];
 
                var path = new google.maps.Polyline({
                    path: points,
                    strokeColor: '#ff0000',
                    strokeOpacity: 1.0,
                    strokeWeight: 4
                });
                path.setMap(map);
 
                var bounds = new google.maps.LatLngBounds();
                for (var i = 0; i < points.length; i++) {
                    bounds.extend(points[i]);
                }
 
                map.fitBounds(bounds);
            }
        </script>
        <style type="text/css">
            #map { height : 300px; width : 500px; }
        </style>
    </head>
    <body onload="initialize()">
        Points: <?php echo count($shape->points()) ?>
        <div id="map"></div>
    </body>
</html>

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)

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

<?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);
?>
<html>
    <head>
        <script type="text/javascript" src="http://maps.google.com/maps/api/js?sensor=false"></script>
        <script type="text/javascript">
            function initialize() {
                var map = new google.maps.Map(
                    document.getElementById('map'),
                    { mapTypeId: google.maps.MapTypeId.ROADMAP }
                );
 
                var points = [
                    <?php foreach ($shape->points() as $k => $point) {  ?>
                        <?php if ($k > 0) {  ?>,<?php } ?>
                        new google.maps.LatLng(<?php echo $point->lat ?>, <?php echo $point->lng ?>)
                    <?php } ?>
                ];
 
                var path = new google.maps.Polyline({
                    path: points,
                    strokeColor: '#ff0000',
                    strokeOpacity: 1.0,
                    strokeWeight: 4
                });
                path.setMap(map);
 
                var bounds = new google.maps.LatLngBounds();
                for (var i = 0; i < points.length; i++) {
                    bounds.extend(points[i]);
                }
 
                map.fitBounds(bounds);
            }
        </script>
        <style type="text/css">
            #map { height : 300px; width : 500px; }
        </style>
    </head>
    <body onload="initialize()">
        Points: <?php echo count($shape->points()) ?>
        <div id="map"></div>
    </body>
</html>

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

Next: Summary

Reducing a Map Path Using Douglas-Peucker Algorithm

A Working Example Using Google Maps

In This Article

Additional Files