/[drupal]/contributions/modules/gmap/gmap_polyutil.inc
ViewVC logotype

Diff of /contributions/modules/gmap/gmap_polyutil.inc

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph | View Patch Patch

revision 1.3, Tue Jul 15 18:00:25 2008 UTC revision 1.4, Mon Apr 6 19:11:59 2009 UTC
# Line 1  Line 1 
1  <?php  <?php
2  // $Id: gmap_polyutil.inc,v 1.2 2008/07/15 16:30:29 bdragon Exp $  // $Id: gmap_polyutil.inc,v 1.3 2008/07/15 18:00:25 bdragon Exp $
3    
4  /**  /**
5   * @file   * @file
# Line 13  Line 13 
13   * [3] http://mathworld.wolfram.com/   * [3] http://mathworld.wolfram.com/
14   */   */
15    
16    DEFINE('GMAP_DP_EPSILON', 0.00001);
17    DEFINE('GMAP_ZOOM_LEVELS', 18);
18    DEFINE('GMAP_ZOOM_FACTOR', 2);
19    
20    
21  /**  /**
22   * Encode a numeric value (steps 3-11 of "Encoding Latitudes and Longitudes" @ [1])   * The following three functions will encode numbers so that they may be used
23     * in "Encoded Polylines" on Google Maps. The encoding is described here:
24     *   http://code.google.com/apis/maps/documentation/polylinealgorithm.html
25     *
26     * Numbers for latitudes/longitudes and levels are encoded slightly
27     * differently--when generating Encoded Polylines, latitudes and longitudes are
28     * encoded with gmap_polyutil_encode_signed(), and "levels" are encoded using
29     * gmap_polyutil_encode_unsigned().
30   */   */
31  function gmap_polyutil_e5_to_encoded($e5) {  function gmap_polyutil_encode_latlon($x) {
32    // As described in http://code.google.com/apis/maps/documentation/polylinealgorithm.html    $x = round($x * 1e5) << 1;
33    $work = $e5; // Make a copy.    if ($x < 0) { $x = ~ $x; }
34    $work <<= 1; // 4) Shift left (Note: I have no clue what happens if PHP_INT_SIZE != 4.)    return _gmap_polyutil_encode($x);
35    if ($e5 < 0) {  }
36      $work = ~$work; // 5) Invert if negative.  
37    }  function gmap_polyutil_encode_levels($x) {
38    $out = '';    return _gmap_polyutil_encode(abs($x));
   // While we are NOT on the last chunk...  
   while ($work >= 32) {  
     // This combines the rest of the steps together.  
     $out .= chr((32 | ($work & 31)) + 63);  
     $work >>= 5;  
   }  
   // Last chunk doesn't get ORed with 32.  
   $out .= chr(($work & 31) + 63);  
   return $out;  
39  }  }
40    
41    function _gmap_polyutil_encode($x) {
42      $result = '';
43      while ($x >= 32) {
44        $result .= chr((32 | ($x & 31)) + 63);
45        $x >>= 5;
46      }
47      $result .= chr(($x & 31) + 63);
48      return $result;
49    }
50    
51    /**
52     * Distance in two dimensions.
53     * √((x1-x0)^2 + (y1-y0)^2)
54     */
55  function gmap_polyutil_dist($p1, $p2) {  function gmap_polyutil_dist($p1, $p2) {
   // Distance in two dimensions.  
   // √((x1-x0)^2 + (y1-y0)^2)  
56    return sqrt(pow($p2[0] - $p1[0], 2) + pow($p2[1] - $p1[1], 2));    return sqrt(pow($p2[0] - $p1[0], 2) + pow($p2[1] - $p1[1], 2));
57  }  }
58    
59  /**  /**
60   * Distance calculation between a point and a line segment.   * Distance between a point and a line segment.
61   * @param $p   * @param $q
62   *   Point to measure.   *   Point to measure.
63   * @param $lp1   * @param $p1
64   *   Point 1 on line.   *   Start point of line segment.
65   * @param $lp2   * @param $p2
66   *   Point 2 on line.   *   End point of line segment.
67   */   */
68  function gmap_polyutil_distance($p, $lp1, $lp2) {  function gmap_polyutil_point_line_dist($q, $p1, $p2) {
69    if ($lp1[0] == $lp2[0] && $lp1[1] == $lp2[1]) {    if ($p1[0] == $p2[0] && $p1[1] == $p2[1]) {
70      // The "line" is really being a point. Just use simple distance.      // lp1 and lp2 are the same point--they don't define a line--so we return
71      return gmap_polyutil_dist($p, $lp1);      // the distance between two points.
72    }      return gmap_polyutil_dist($q, $p1);
73    // mathematica code: (q-p1).(p2-p1)/(p2-p1).(p2-p1);    }
74    // I asked maxima, and it said ((p2y-p1y)*(qy-p1y)+(p2x-p1x)*(qx-p1x))/((p2y-p1y)^2+(p2x-p1x)^2).  
75    $tmp = (($lp2[1]-$lp1[1])*($p[1]-$lp1[1])+($lp2[0]-$lp1[0])*($p[0]-$lp1[0]))/(pow($lp2[1]-$lp1[1], 2) + pow($lp2[0]-$lp1[0], 2));    // Use the dot product to find where q lies with respect to the line segment
76    // Point is not alongside segment, is further off in $lp1's direction.    // p1p2. For more information, see:
77    if ($tmp <= 0) {    //   http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
78      return gmap_polyutil_dist($lp1, $p);    //   http://www.codeguru.com/forum/printthread.php?t=194400
79    }    $u = (($p2[1]-$p1[1])*($q[1]-$p1[1]) + ($p2[0]-$p1[0])*($q[0]-$p1[0])) / (pow($p2[1]-$p1[1], 2) + pow($p2[0]-$p1[0], 2));
80    // Point is not alongside segment, is further off in $lp2's direction.  
81    else if ($tmp >= 1) {    if ($u <= 0) { // point is not alongside segment, it is further off in $p1's direction
82      return gmap_polyutil_dist($lp2, $p);      return gmap_polyutil_dist($q, $p1);
83    }    }
84    else {    elseif ($u >= 1) { // point is not alongside segment, it is further off in $p2's direction
85      // mathematica code: Norm[q-(p1+u (p2-p1))]      return gmap_polyutil_dist($q, $p2);
86      // which means q and (p1+u (p2-p1)) are the things we are calculating distance on.    }
87      // maxima sez: (p1+u*(p2-p1)) => [(p2x-p1x)*u+p1x,(p2y-p1y)*u+p1y]    else { // point is alongside segment
88      return gmap_polyutil_dist($p, array(($lp2[0]-$lp1[0])*$tmp + $lp1[0], ($lp2[1]-$lp1[1])*$tmp + $lp1[1]));      // calculate distance between q and the nearest point on the line segment
89        // use $u to calculate the nearest point on the line segment:
90        //   p1 + u*(p2 - p1) => [p1x + u*(p2x - p1x), p1y + u*(p2y - p1y)]
91        return gmap_polyutil_dist($q, array( $p1[0] + $u*($p2[0] - $p1[0]), $p1[1] + $u*($p2[1] - $p1[1])));
92      }
93    }
94    
95    /**
96     * Implementation of the Douglas-Peucker polyline simplification algorithm. See:
97     * http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/algorithm.html
98     *
99     * @param $points
100     *   An array of coordinate pairs.
101     * @return
102     *   An array of keys => weights; the keys correspond with indices of points in
103     *   the $points array. Some points may be insignificant according to the
104     *   algorithm--they will not have entries in the return array. The "weights"
105     *   are actually the point's distance from the line segment that it subdivides.
106     */
107    function gmap_polyutil_dp_encode($points) {
108      $weights = array();
109    
110      if (count($points) > 2) {
111        // the 'stack' holds line segments to be simplified
112        $stack[] = array(0, count($points) - 1);
113    
114        while (count($stack) > 0) {
115          // take a line segment to look at
116          $segment = array_pop($stack);
117    
118          // figure out which subdividing point is the furthest off the line segment
119          $max_dist = 0;
120          for ($i = $segment[0] + 1; $i < $segment[1]; $i++) {
121            $dist = gmap_polyutil_point_line_dist($points[$i], $points[$segment[0]], $points[$segment[1]]);
122            if ($dist > $max_dist) {
123              $max_dist = $dist;
124              $max_i = $i;
125            }
126          }
127    
128          // if the subdividing point found above is significantly off the line
129          // segment then we want to simplify further. Add sub-segments to the stack.
130          if ($max_dist > GMAP_DP_EPSILON) {
131            $weights[$max_i] = $max_dist;
132            array_push($stack, array($segment[0], $max_i));
133            array_push($stack, array($max_i, $segment[1]));
134          }
135        }
136      }
137    
138      // The first and last points of the line should always be visible.
139      $levels = _gmap_polyutil_zoom_levels();
140      $weights[0] = $levels[0];
141      $weights[count($points) -1] = $levels[0];
142    
143      return $weights;
144    }
145    
146    /**
147     * Simplify a set of points and generate an "Encoded Polyline" for Google Maps.
148     * @param $points
149     *   An array of coordinate pairs as latitude, longitude.
150     * @return
151     *   An array containing the point and zoom information necessary to display
152     *   encoded polylines on Google Maps: 'points', 'levels', 'numLevels', and 'zoomFactor'.
153     */
154    function gmap_polyutil_polyline($points) {
155      $points_encoded = '';
156      $levels_encoded = '';
157    
158      // simplify the line
159      $weights = gmap_polyutil_dp_encode($points);
160    
161      $previous = array(0, 0);
162      foreach ($points as $i => $p) {
163        if (isset($weights[$i])) {
164          // encode each simplified point
165          // the deltas between points are encoded, rather than the point values themselves
166          $points_encoded .= gmap_polyutil_encode_latlon($p[0] - $previous[0]) . gmap_polyutil_encode_latlon($p[1] - $previous[1]);
167          $levels_encoded .= gmap_polyutil_encode_levels(_gmap_polyutil_get_zoom_level($weights[$i]));
168          $previous = $p;
169        }
170      }
171    
172      return array(
173        'points' => $points_encoded,
174        'levels' => $levels_encoded,
175        'numLevels' => GMAP_ZOOM_LEVELS,
176        'zoomFactor' => GMAP_ZOOM_FACTOR,
177      );
178    }
179    
180    /**
181     * Build a logarithmic scale of zoom levels.
182     */
183    function _gmap_polyutil_zoom_levels() {
184      static $levels;
185      if (!isset($levels)) {
186        for ($i = 0; $i < GMAP_ZOOM_LEVELS; $i++) {
187          $levels[$i] = GMAP_DP_EPSILON * pow(GMAP_ZOOM_FACTOR, GMAP_ZOOM_LEVELS - $i - 1);
188        }
189      }
190      return $levels;
191    }
192    
193    /**
194     * Place points in levels based on their "weight" -- a value derived from
195     * distance calculations in the simplification algorithm, gmap_polyutil_dp_encode().
196     */
197    function _gmap_polyutil_get_zoom_level($weight) {
198      $levels = _gmap_polyutil_zoom_levels();
199      $i = 0;
200      while ($levels[$i] > $weight) {
201        $i++;
202    }    }
203      return GMAP_ZOOM_LEVELS - $i - 1;
204  }  }
Legend:
Removed from v.1.3  
changed lines
  Added in v.1.4
  ViewVC Help
Powered by ViewVC 1.1.2