Class: GMapPolylineEncoder

Inherits:
Object
  • Object
show all
Defined in:
lib/gmap_polyline_encoder.rb

Overview

–

Utility for creating Google Maps Encoded GPolylines facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/gmap_polyline_encoder.rb.txt

License: You may distribute this code under the same terms as Ruby itself

Author: Joel Rosenberg

( Drawing from the official example pages as well as Mark McClure’s work )

Example

data = [
  [ 37.4419, -122.1419],
  [ 37.4519, -122.1519],
  [ 37.4619, -122.1819],
]

encoder = GMapPolylineEncoder.new()
result = encoder.encode( data )

javascript << "  var myLine = new GPolyline.fromEncoded({\n"
javascript << "     color: \"#FF0000\",\n"
javascript << "     weight: 10,\n"
javascript << "     opacity: 0.5,\n"
javascript << "     zoomFactor: #{result[:zoomFactor]},\n"
javascript << "     numLevels: #{result[:numLevels]},\n"
javascript << "     points: \"#{result[:points]}\",\n"
javascript << "     levels: \"#{result[:levels]}\"\n"
javascript << "  });"

Methods

Constructor args (all optional): 
  :numLevels (default 18)
  :zoomFactor (default 2)
  :reduce: Reduce points (default true)
  :escape: Escape backslashes (default true)

encode( points ) method
  points (required): array of longitude, latitude pairs

  returns hash with keys :points, :levels, :zoomFactor, :numLevels

Background

Description: www.google.com/apis/maps/documentation/#Encoded_Polylines API: www.google.com/apis/maps/documentation/reference.html#GPolyline Hints: www.google.com/apis/maps/documentation/polylinealgorithm.html

Example Javascript for instantiating an encoded polyline: var encodedPolyline = new GPolyline.fromEncoded( 

color: "#FF0000",
weight: 10,
points: "yzocFzynhVq@n}@o}@nzD",
levels: "BBB",
zoomFactor: 32,
numLevels: 4

});

Changes

06.29.2007 - Release 0.1

Profiling showed that distance() accounted for 50% of the time when
processing McClure's British coast data. By moving the distance
calculation into encode(), we can cache a few of the calculations
(magnitude) and eliminate the overhead of the function call. This
reduced the time to encode by ~ 30%

06.21.2007 Implementing the Doublas-Peucker algorithm for removing superflous

points as per Mark McClure's design:
    http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/

10.14.2006 Cleaned up (and finally grasped) zoom levels

09.2006 First port of the official example’s javascript. Ignoring zoom

levels for now, showing points at all zoom levels

++

Constant Summary collapse

@@dp_threshold =

The minimum distance from the line that a point must exceed to avoid elimination under the DP Algorithm.

0.00001

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options = {}) ⇒ GMapPolylineEncoder

Returns a new instance of GMapPolylineEncoder.



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/gmap_polyline_encoder.rb', line 90

def initialize(options = {})
  # There are no required parameters

  # Nice defaults
  @numLevels  = options.has_key?(:numLevels)  ? options[:numLevels]  : 18
  @zoomFactor = options.has_key?(:zoomFactor) ? options[:zoomFactor] : 2
  
  # Calculate the distance thresholds for each zoom level
  calculate_zoom_breaks()
  
  # By default we'll simplify the polyline unless told otherwise
  @reduce = ! options.has_key?(:reduce) ? true : options[:reduce]
  
  # Escape by default; most people are using this in a web context
  @escape = ! options.has_key?(:escape) ? true : options[:escape]
  
end

Instance Attribute Details

#escape ⇒ Object

zoomFactor and numLevels need side effects



83
84
85
 
# File 'lib/gmap_polyline_encoder.rb', line 83

def escape
  @escape
end

#numLevels ⇒ Object

Returns the value of attribute numLevels.



84
85
86
 
# File 'lib/gmap_polyline_encoder.rb', line 84

def numLevels
  @numLevels
end

#reduce ⇒ Object

zoomFactor and numLevels need side effects



83
84
85
 
# File 'lib/gmap_polyline_encoder.rb', line 83

def reduce
  @reduce
end

#zoomFactor ⇒ Object

Returns the value of attribute zoomFactor.



84
85
86
 
# File 'lib/gmap_polyline_encoder.rb', line 84

def zoomFactor
  @zoomFactor
end

Instance Method Details

#encode(points) ⇒ Object 



120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
 
# File 'lib/gmap_polyline_encoder.rb', line 120

def encode( points )

  #
  # This is an implementation of the Douglas-Peucker algorithm for simplifying
  # a line. You can thing of it as an elimination of points that do not
  # deviate enough from a vector. That threshold for point elimination is in
  # @@dp_threshold. See
  #
  #   http://everything2.com/index.pl?node_id=859282
  #
  # for an explanation of the algorithm
  #
  
  max_dist = 0  # Greatest distance we measured during the run
  stack = []
  distances = Array.new(points.size)

  if(points.length > 2)
    stack << [0, points.size-1]
    
    while(stack.length > 0) 
      current_line = stack.pop()
      p1_idx = current_line[0]
      pn_idx = current_line[1]
      pb_dist = 0
      pb_idx = nil
      
      x1 = points[p1_idx][0]
      y1 = points[p1_idx][1]
      x2 = points[pn_idx][0]
      y2 = points[pn_idx][1]
      
      # Caching the line's magnitude for performance
      magnitude = Math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
      magnitude_squared = magnitude ** 2
      
      # Find the farthest point and its distance from the line between our pair
      for i in (p1_idx+1)..(pn_idx-1)
      
        # Refactoring distance computation inline for performance
        #current_distance = compute_distance(points[i], points[p1_idx], points[pn_idx])
        
        # 
        # This uses Euclidian geometry. It shouldn't be that big of a deal since
        # we're using it as a rough comparison for line elimination and zoom
        # calculation.
        #
        # TODO: Implement Haversine functions which would probably bring this to
        #       a snail's pace (ehhhh)
        #
  
        px = points[i][0]
        py = points[i][1]
       
        current_distance = nil
        
        if( magnitude == 0 )
          # The line is really just a point
          current_distance = Math.sqrt((x2-px)**2 + (y2-py)**2)
        else
       
          u = (((px - x1) * (x2 - x1)) + ((py - y1) * (y2 - y1))) / magnitude_squared
          
          if( u <= 0 || u > 1 )
              # The point is closest to an endpoint. Find out which one
              ix = Math.sqrt((x1 - px)**2 + (y1 - py)**2)
              iy = Math.sqrt((x2 - px)**2 + (y2 - py)**2)
              if( ix > iy )
                current_distance = iy
              else
                current_distance = ix
              end
          else
              # The perpendicular point intersects the line
              ix = x1 + u * (x2 - x1)
              iy = y1 + u * (y2 - y1)
              current_distance = Math.sqrt((ix - px)**2 + (iy - py)**2)
          end
        end
        
        # See if this distance is the greatest for this segment so far
        if(current_distance > pb_dist)
          pb_dist = current_distance
          pb_idx = i
        end
      end
      
      # See if this is the greatest distance for all points
      if(pb_dist > max_dist)
        max_dist = pb_dist
      end
      
      if(pb_dist > @@dp_threshold)
        # Our point, Pb, that had the greatest distance from the line, is also
        # greater than our threshold. Process again using Pb as a new 
        # start/end point. Record this distance - we'll use it later when
        # creating zoom values
        distances[pb_idx] = pb_dist
        stack << [p1_idx, pb_idx]
        stack << [pb_idx, pn_idx]
      end
      
    end
  end
  
  # Force line endpoints to be included (sloppy, but faster than checking for
  # endpoints in encode_points())
  distances[0] = max_dist
  distances[distances.length-1] = max_dist

  # Create Base64 encoded strings for our points and zoom levels
  points_enc = encode_points( points, distances)
  levels_enc = encode_levels( points, distances, max_dist)
  
  # Make points_enc an escaped string if desired.
  # We should escape the levels too, in case google pulls a switcheroo
  @escape && points_enc && points_enc.gsub!( /\\/, '\\\\\\\\' )
 
  
  # Returning a hash. Yes, I am a Perl programmer
  return {
    :points     => points_enc,
    :levels     => levels_enc,
    :zoomFactor => @zoomFactor,
    :numLevels  => @numLevels,
  }
  
end