Class: GoogleStaticMapsHelper::GMapPolylineEncoder

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

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.



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

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



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

def escape
  @escape
end

#numLevels ⇒ Object

Returns the value of attribute numLevels.



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

def numLevels
  @numLevels
end

#reduce ⇒ Object

zoomFactor and numLevels need side effects



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

def reduce
  @reduce
end

#zoomFactor ⇒ Object

Returns the value of attribute zoomFactor.



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

def zoomFactor
  @zoomFactor
end

Instance Method Details

#encode(points) ⇒ Object 



119
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
 
# File 'lib/google_static_maps_helper/gmap_polyline_encoder.rb', line 119

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