function gmap_polyutil_dp_encode in GMap Module 6

Same name and namespace in other branches

1. 5 gmap_polyutil.inc \gmap_polyutil_dp_encode()
2. 6.2 gmap_polyutil.inc \gmap_polyutil_dp_encode()
3. 7.2 gmap_polyutil.inc \gmap_polyutil_dp_encode()
4. 7 gmap_polyutil.inc \gmap_polyutil_dp_encode()

Implementation of the Douglas-Peucker polyline simplification algorithm. See: http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/algorithm.html

Parameters

$points: An array of coordinate pairs.

Return value

An array of keys => weights; the keys correspond with indices of points in the $points array. Some points may be insignificant according to the algorithm--they will not have entries in the return array. The "weights" are actually the point's distance from the line segment that it subdivides.

1 call to gmap_polyutil_dp_encode()

gmap_polyutil_polyline in ./gmap_polyutil.inc

Simplify a set of points and generate an "Encoded Polyline" for Google Maps.

File

./gmap_polyutil.inc, line 106

Encoded polyline utilities.

Code

function gmap_polyutil_dp_encode($points) {
  $weights = array();
  if (count($points) > 2) {

    // the 'stack' holds line segments to be simplified
    $stack[] = array(
      0,
      count($points) - 1,
    );
    while (count($stack) > 0) {

      // take a line segment to look at
      $segment = array_pop($stack);

      // figure out which subdividing point is the furthest off the line segment
      $max_dist = 0;
      for ($i = $segment[0] + 1; $i < $segment[1]; $i++) {
        $dist = gmap_polyutil_point_line_dist($points[$i], $points[$segment[0]], $points[$segment[1]]);
        if ($dist > $max_dist) {
          $max_dist = $dist;
          $max_i = $i;
        }
      }

      // if the subdividing point found above is significantly off the line
      // segment then we want to simplify further. Add sub-segments to the stack.
      if ($max_dist > GMAP_DP_EPSILON) {
        $weights[$max_i] = $max_dist;
        array_push($stack, array(
          $segment[0],
          $max_i,
        ));
        array_push($stack, array(
          $max_i,
          $segment[1],
        ));
      }
    }
  }

  // The first and last points of the line should always be visible.
  $levels = _gmap_polyutil_zoom_levels();
  $weights[0] = $levels[0];
  $weights[count($points) - 1] = $levels[0];
  return $weights;
}