Changeset 886

Timestamp:

05/12/07 15:49:33 (5 years ago)

Author:

bycycle

Message:

Added proper levels encoding using info/algorithms from
 http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/

Updated Route entity to use the properly encoded levels instead of just
hardcoding all Ps

Location:

core/trunk/byCycle/model

Files:

• glineenc.py (modified) (7 diffs)
• route.py (modified) (2 diffs)

core/trunk/byCycle/model/glineenc.py

@@ -1 @@
-def encode_pairs(pairs):
-    """Encode a set of lat/long pairs.
+import math
 
-    ``pairs``
-        A list of lat/long pairs ((lat, long), ...)
+
+threshold = .00001
+num_levels = 4
+zoom_factor = 32
+zoom_level_breaks = []
+for i in range(num_levels):
+    zoom_level_breaks.append(threshold * (zoom_factor ** (num_levels - i - 1)))
+    
+
+def encode_pairs(points):
+    """Encode a set of lat/long points.
+
+    ``points``
+        A list of lat/long points ((lat, long), ...)
         Note carefully that the order is latitude, longitude
 
     return
-        An encoded string representing all pairs
+        - An encoded string representing points within our error
+          ``threshold``,
+        - An encoded string representing the maximum zoom level for each of
+          those points
 
     Example::
@@ -13 +27 @@
         >>> pairs = ((38.5, -120.2), (43.252, -126.453), (40.7, -120.95))
         >>> encode_pairs(pairs)
-        '_p~iF~ps|U_c_\\\\fhde@~lqNwxq`@'
+        ('_p~iF~ps|U_c_\\\\fhde@~lqNwxq`@', 'BBB')
 
     """
-    result = []
+    encoded_points = []
+    encoded_levels = []
+    
+    distances = douglas_peucker_distances(points)
+    points_of_interest = []
+    for i, d in enumerate(distances):
+        if d is not None:
+            lat, long = points[i]
+            points_of_interest.append((lat, long, d))
+    
     lat_prev, long_prev = 0, 0
-    for pair in pairs:
-        encoded_val, lat_prev = encode(pair[0], lat_prev)
-        result.append(encoded_val)
-        encoded_val, long_prev = encode(pair[1], long_prev)
-        result.append(encoded_val)
-    result = ''.join(result)
-    return result
+    for lat, long, d in points_of_interest:
+        encoded_lat, lat_prev = encode_lat_or_long(lat, lat_prev)
+        encoded_long, long_prev = encode_lat_or_long(long, long_prev)
+        encoded_points += [encoded_lat, encoded_long]
+        encoded_level = encode_unsigned(num_levels - compute_level(d) - 1)
+        encoded_levels.append(encoded_level)
 
-def encode(x, prev_int):
+    encoded_points_str = ''.join(encoded_points)
+    encoded_levels_str = ''.join([str(l) for l in encoded_levels])
+    return encoded_points_str, encoded_levels_str
+
+def encode_lat_or_long(x, prev_int):
     """Encode a single latitude or longitude.
     
@@ -33 +59 @@
         
     ``prev_int``
-        The int value of the previous latitude or longitude
+        The integer value of the previous latitude or longitude
         
     Return the encoded value and its int value, which is used
@@ -40 +66 @@
     
         >>> x = -179.9832104
-        >>> encoded_x, prev = encode(x, 0)
+        >>> encoded_x, prev = encode_lat_or_long(x, 0)
         >>> encoded_x
         '`~oia@'
@@ -46 +72 @@
         -17998321
         >>> x = -120.2
-        >>> encode(x, prev)
+        >>> encode_lat_or_long(x, prev)
         ('al{kJ', -12020000)
     
     """
     int_value = int(x * 1e5)
-    res = int_value - prev_int
-    res = res << 1
-    if res < 0:
-        res = ~res
-    chunk = res
-    res = []
+    delta = int_value - prev_int
+    return encode_signed(delta), int_value
+
+def encode_signed(n):
+    tmp = n << 1
+    if n < 0:
+        tmp = ~tmp
+    return encode_unsigned(tmp)
+
+def encode_unsigned(n):
+    tmp = []
     # while there are more than 5 bits left (that aren't all 0)...
-    while chunk >= 32:  # 32 == 0xf0 == 100000
-        res.append(chunk & 31)  # 31 == 0x1f == 11111
-        chunk = chunk >> 5
-    res = [(c | 0x20) for c in res]
-    res.append(chunk)
-    res = [(i + 63) for i in res]
-    res = [chr(i) for i in res]
-    res = ''.join(res)
-    return res, int_value
+    while n >= 32:  # 32 == 0xf0 == 100000
+        tmp.append(n & 31)  # 31 == 0x1f == 11111
+        n = n >> 5
+    tmp = [(c | 0x20) for c in tmp]
+    tmp.append(n)
+    tmp = [(i + 63) for i in tmp]
+    tmp = [chr(i) for i in tmp]
+    tmp = ''.join(tmp)
+    return tmp    
+
+def douglas_peucker_distances(points):
+    distances = [None] * len(points)
+    distances[0] = threshold * (zoom_factor ** num_levels)
+    distances[-1] = distances[0]
+
+    if(len(points) < 3):
+        return distances
+
+    stack = [(0, len(points) - 1)]
+    while stack:
+        a, b = stack.pop()
+        max_dist = 0
+        for i in range(a + 1, b):
+            dist = distance(points[i], points[a], points[b])
+            if dist > max_dist:
+                max_dist = dist
+                max_i = i
+        if max_dist > threshold:
+            distances[max_i] = max_dist
+            stack += [(a, max_i), (max_i, b)]
+
+    return distances
+
+def distance(point, A, B):
+    """Compute distance of ``point`` from line ``A``, ``B``."""
+    if A == B:
+        out = math.sqrt(
+            (B[0] - point[0]) ** 2 +
+            (B[1] - point[1]) ** 2
+        )
+    else:
+        u = (
+            (((point[0] - A[0]) * (B[0] - A[0])) +
+             ((point[1] - A[1]) * (B[1] - A[1]))) / 
+            (((B[0] - A[0]) ** 2) +  ((B[1] - A[1]) ** 2))
+        )
+        if u <= 0:
+            out = math.sqrt(
+                ((point[0] - A[0]) ** 2) + ((point[1] - A[1]) ** 2)
+            )
+        elif u >= 1:
+            out = math.sqrt(
+                ((point[0] - B[0]) ** 2) + ((point[1] - B[1]) ** 2)
+            )
+        elif 0 < u < 1:
+            out = math.sqrt(
+                ((((point[0] - A[0]) - (u * (B[0] - A[0]))) ** 2)) +
+                ((((point[1] - A[1]) - (u * (B[1] - A[1]))) ** 2))
+            )
+    return out
+
+def compute_level(distance):
+    """Compute the appropriate zoom level of a point in terms of its 
+    distance from the relevant segment in the DP algorithm."""
+    if distance > threshold:
+        level = 0
+    while distance < zoom_level_breaks[level]:
+        level += 1
+    return level
 
 def test_encode_negative():
     f = -179.9832104
-    assert encode(f, 0)[0] == '`~oia@'
+    assert encode_lat_or_long(f, 0)[0] == '`~oia@'
     
     f = -120.2
-    assert encode(f, 0)[0] == '~ps|U'
+    assert encode_lat_or_long(f, 0)[0] == '~ps|U'
 
 def test_encode_positive():
     f = 38.5
-    assert encode(f, 0)[0] == '_p~iF'
+    assert encode_lat_or_long(f, 0)[0] == '_p~iF'
 
 def test_encode_one_pair():
     pairs = [(38.5, -120.2)]
-    expected_encoding = '_p~iF~ps|U'
+    expected_encoding = '_p~iF~ps|U', 'B'
     assert encode_pairs(pairs) == expected_encoding
 
@@ -91 +182 @@
         (40.7, -120.95),
     )
-    expected_encoding = '_p~iF~ps|U_ulLnnqC_mqNvxq`@~lqNwxq`@'
+    expected_encoding = '_p~iF~ps|U_ulLnnqC_mqNvxq`@~lqNwxq`@', 'BBBB'
     assert encode_pairs(pairs) == expected_encoding
     
@@ -99 +190 @@
         (37.4619, -122.1819),
     )
-    expected_encoding = 'yzocFzynhVq}@n}@o}@nzD'
+    expected_encoding = 'yzocFzynhVq}@n}@o}@nzD', 'B@B'
     assert encode_pairs(pairs) == expected_encoding    

core/trunk/byCycle/model/route.py

@@ -49 +49 @@
         bounds = self.linestring_ll.envelope()
         centroid = bounds.centroid()
+        google_points, google_levels = glineenc.encode_pairs(pairs)
         route = {
             'start': dict(self.start),
@@ -60 +61 @@
             'directions': self.directions,
             'distance': self.distance,
-            'google_points': glineenc.encode_pairs(pairs),
-            'google_levels': 'P' * len(pairs),
+            'google_points': google_points,
+            'google_levels': google_levels,
         }
         route['start']['geocode'] = route['start']['geocode'].to_builtin()