function legacy_gmap_polyutil_dp_encode in GMap Module 7.2

Implementation of the Douglas-Peucker polyline simplification algorithm.

See: http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/algorithm.html

Parameters

array $points: An array of coordinate pairs.

Return value

array 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 legacy_gmap_polyutil_dp_encode()

legacy_gmap_polyutil_polyline in tests/inc/gmap_polyutil.inc

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

File

tests/inc/gmap_polyutil.inc, line 132

Encoded polyline utilities.

Namespace

tests\inc

Code

function legacy_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 = legacy_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 = legacy__gmap_polyutil_zoom_levels();
  $weights[0] = $levels[0];
  $weights[count($points) - 1] = $levels[0];
  return $weights;
}