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