Subversion Repositories eFlore/Projets.communes

<?php
/*========================================================
/* Implementation of Douglas-Peuker in PHP.
/* 
/* Anthony Cartmell
/* ajcartmell@fonant.com
/* 
/* This software is provided as-is, with no warranty.
/* Please use and modify freely for anything you like :)
/* Version 1.2 - 18 Aug 2009  Fixes problem with line of three points.
/*                                                      Thanks to Craig Stanton http://craig.stanton.net.nz
/* Version 1.1 - 17 Jan 2007  Fixes nasty bug!
/*========================================================*/

class PolylineReducer {
        private $original_points = array();
        private $tolerance;
        private $tolerance_squared;

        public function __construct($geopoints_array) {
                foreach ($geopoints_array as $point) {
                        $this->original_points[] = new Vector($point->latitude, $point->longitude);
                }
                /*----- Include first and last points -----*/
                $this->original_points[0]->include = true;
                $this->original_points[count($this->original_points)-1]->include = true;
        }

        /**
        * Returns a list of GeoPoints for the simplest polyline that leaves
        * no original point more than $tolerance away from it.
        *
        * @param float  $tolerance
        * @return Geopoint array
        */
        public function SimplerLine($tolerance = 0.5) {
                $this->tolerance = $tolerance;
                $this->tolerance_squared = $tolerance * $tolerance;
                $this->DouglasPeucker(0, count($this->original_points) - 1);
                foreach ($this->original_points as $point) {
                        if ($point->include) {
                                $out[] = new GeoPoint($point->x, $point->y);
                        }
                }
                return $out;
        }

        /**
        * Douglas-Peuker polyline simplification algorithm. First draws single line
        * from start to end. Then finds largest deviation from this straight line, and if
        * greater than tolerance, includes that point, splitting the original line into
        * two new lines. Repeats recursively for each new line created.
        *
        * @param int $start_vertex_index
        * @param int $end_vertex_index
        */
        private function DouglasPeucker($start_vertex_index, $end_vertex_index) {
                if ($end_vertex_index <= $start_vertex_index + 1) // there is nothing to simplify
                return;

                // Make line from start to end
                $line = new Line($this->original_points[$start_vertex_index], $this->original_points[$end_vertex_index]);

                // Find largest distance from intermediate points to this line
                $max_dist_to_line_squared = 0;
                for ($index = $start_vertex_index+1; $index < $end_vertex_index; $index++) {
                        $dist_to_line_squared = $line->DistanceToPointSquared($this->original_points[$index]);
                        if ($dist_to_line_squared>$max_dist_to_line_squared) {
                                $max_dist_to_line_squared = $dist_to_line_squared;
                                $max_dist_index = $index;
                        }
                }

                // Check max distance with tolerance
                if ($max_dist_to_line_squared > $this->tolerance_squared) {// error is worse than the tolerance
                        // split the polyline at the farthest vertex from S
                        $this->original_points[$max_dist_index]->include = true;
                        // recursively simplify the two subpolylines
                        $this->DouglasPeucker($start_vertex_index,$max_dist_index);
                        $this->DouglasPeucker($max_dist_index,$end_vertex_index);
                }
                // else the approximation is OK, so ignore intermediate vertices
        }
}
?>