| 1 |
<?php
|
| 2 |
// $Id: gmap_polyutil.inc,v 1.3 2008/07/15 18:00:25 bdragon Exp $
|
| 3 |
|
| 4 |
/**
|
| 5 |
* @file
|
| 6 |
* Encoded polyline utilities.
|
| 7 |
*/
|
| 8 |
|
| 9 |
/**
|
| 10 |
* References:
|
| 11 |
* [1] http://code.google.com/apis/maps/documentation/polylinealgorithm.html
|
| 12 |
* [2] http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/
|
| 13 |
* [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 |
* 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_encode_latlon($x) {
|
| 32 |
$x = round($x * 1e5) << 1;
|
| 33 |
if ($x < 0) { $x = ~ $x; }
|
| 34 |
return _gmap_polyutil_encode($x);
|
| 35 |
}
|
| 36 |
|
| 37 |
function gmap_polyutil_encode_levels($x) {
|
| 38 |
return _gmap_polyutil_encode(abs($x));
|
| 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) {
|
| 56 |
return sqrt(pow($p2[0] - $p1[0], 2) + pow($p2[1] - $p1[1], 2));
|
| 57 |
}
|
| 58 |
|
| 59 |
/**
|
| 60 |
* Distance between a point and a line segment.
|
| 61 |
* @param $q
|
| 62 |
* Point to measure.
|
| 63 |
* @param $p1
|
| 64 |
* Start point of line segment.
|
| 65 |
* @param $p2
|
| 66 |
* End point of line segment.
|
| 67 |
*/
|
| 68 |
function gmap_polyutil_point_line_dist($q, $p1, $p2) {
|
| 69 |
if ($p1[0] == $p2[0] && $p1[1] == $p2[1]) {
|
| 70 |
// lp1 and lp2 are the same point--they don't define a line--so we return
|
| 71 |
// the distance between two points.
|
| 72 |
return gmap_polyutil_dist($q, $p1);
|
| 73 |
}
|
| 74 |
|
| 75 |
// Use the dot product to find where q lies with respect to the line segment
|
| 76 |
// p1p2. For more information, see:
|
| 77 |
// http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
|
| 78 |
// 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 |
|
| 81 |
if ($u <= 0) { // point is not alongside segment, it is further off in $p1's direction
|
| 82 |
return gmap_polyutil_dist($q, $p1);
|
| 83 |
}
|
| 84 |
elseif ($u >= 1) { // point is not alongside segment, it is further off in $p2's direction
|
| 85 |
return gmap_polyutil_dist($q, $p2);
|
| 86 |
}
|
| 87 |
else { // point is alongside segment
|
| 88 |
// 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 |
}
|
Parent Directory
| 
Revision Log
| 
Revision Graph