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