Added Wkb fallback to StringCompressedPolyLine for when compression a…

…lgo fails
osmlab · matthieun · Aug 22, 2018 · Aug 16, 2018 · Aug 17, 2018 · Aug 17, 2018
commit 4f9faa3d88a700b42554030e89ec8599f65b1189
diff --git a/src/main/java/org/openstreetmap/atlas/geography/PolyLine.java b/src/main/java/org/openstreetmap/atlas/geography/PolyLine.java
@@ -17,6 +17,8 @@
 import org.openstreetmap.atlas.geography.Snapper.SnappedLocation;
 import org.openstreetmap.atlas.geography.clipping.Clip;
 import org.openstreetmap.atlas.geography.clipping.Clip.ClipType;
+import org.openstreetmap.atlas.geography.converters.WkbLocationConverter;
+import org.openstreetmap.atlas.geography.converters.WkbPolyLineConverter;
 import org.openstreetmap.atlas.geography.converters.WktLocationConverter;
 import org.openstreetmap.atlas.geography.converters.WktPolyLineConverter;
 import org.openstreetmap.atlas.geography.geojson.GeoJsonBuilder;
@@ -87,6 +89,18 @@ public static void saveAsGeoJson(final Iterable<? extends Iterable<Location>> ge
         }
     }
 
+    /**
+     * Create a {@link PolyLine} from Well Known Binary
+     *
+     * @param wkb
+     *            The Well Known Binary
+     * @return The {@link PolyLine}
+     */
+    public static PolyLine wkb(final byte[] wkb)
+    {
+        return new WkbPolyLineConverter().backwardConvert(wkb);
+    }
+
     /**
      * Create a {@link PolyLine} from Well Known Text
      *
@@ -1106,6 +1120,19 @@ public String toString()
         return toWkt();
     }
 
+    /**
+     * @return This {@link PolyLine} as Well Known Binary
+     */
+    public byte[] toWkb()
+    {
+        if (this.size() == 1)
+        {
+            // Handle a single location polyLine
+            return new WkbLocationConverter().convert(this.first());
+        }
+        return new WkbPolyLineConverter().convert(this);
+    }
+
     /**
      * @return This {@link PolyLine} as Well Known Text
      */

diff --git a/src/main/java/org/openstreetmap/atlas/geography/StringCompressedPolyLine.java b/src/main/java/org/openstreetmap/atlas/geography/StringCompressedPolyLine.java
@@ -5,11 +5,20 @@
 import java.util.List;
 
 import org.openstreetmap.atlas.exception.CoreException;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
 
 /**
- * Derived from MapQuest's developer portal:
- * https://developer.mapquest.com/documentation/common/encode-decode/
+ * Encode a {@link PolyLine} using an algorithm derived from the MapQuest variant of the Google
+ * Polyline Encoding Format. The encoding scheme falls back on WKB in edge cases when the algorithm
+ * fails (such as when two consecutive points in the polyline have a longitude difference of greater
+ * than 180 degrees).
  *
+ * @see <a href="https://developer.mapquest.com/documentation/common/encode-decode">The MapQuest
+ *      algorithm</a>
+ * @see <a href=
+ *      "https://developers.google.com/maps/documentation/utilities/polylinealgorithm?csw=1">Google
+ *      Polyline Encoding Format</a>
  * @author matthieun
  */
 public class StringCompressedPolyLine implements Serializable
@@ -42,7 +51,13 @@ public PolyLineCompressionException(final String message, final Object... items)
     private static final long MAXIMUM_DELTA_LONGITUDE = (long) (MAXIMUM_DELTA_LONGITUDE_IN_DEGREES
             * Math.pow(10, PRECISION));
 
-    private final byte[] encoding;
+    // if the first byte of the encoding array is this sentinel value, then the following encoding
+    // is WKB and not string compressed
+    private static final byte WKB_SENTINEL = 0;
+
+    private static final Logger logger = LoggerFactory.getLogger(StringCompressedPolyLine.class);
+
+    private byte[] encoding;
 
     public StringCompressedPolyLine(final byte[] encoding)
     {
@@ -55,25 +70,34 @@ public StringCompressedPolyLine(final PolyLine polyLine)
         {
             this.encoding = compress(polyLine, PRECISION).getBytes(ENCODING_NAME);
         }
-        catch (final PolyLineCompressionException e)
+        catch (final PolyLineCompressionException exception)
         {
-            throw e;
+            this.encoding = getWkbFallback(polyLine);
         }
-        catch (final Exception e)
+        catch (final Exception exception)
         {
-            throw new CoreException("Could not compress polyline.", e);
+            throw new CoreException("Could not compress polyline.", exception);
         }
     }
 
     public PolyLine asPolyLine()
     {
-        try
+        if (this.encoding[0] == WKB_SENTINEL)
         {
-            return asPolyLine(new String(this.encoding, ENCODING_NAME), PRECISION);
+            final byte[] strippedEncoding = new byte[this.encoding.length - 1];
+            System.arraycopy(this.encoding, 1, strippedEncoding, 0, strippedEncoding.length);
+            return PolyLine.wkb(strippedEncoding);
         }
-        catch (final Exception e)
+        else
         {
-            throw new CoreException("Could not decompress polyline.", e);
+            try
+            {
+                return asPolyLine(new String(this.encoding, ENCODING_NAME), PRECISION);
+            }
+            catch (final Exception exception)
+            {
+                throw new CoreException("Could not decompress polyline.", exception);
+            }
         }
     }
 
@@ -85,13 +109,22 @@ public byte[] getEncoding()
     @Override
     public String toString()
     {
-        try
+        if (this.encoding[0] == WKB_SENTINEL)
         {
-            return new String(this.encoding, ENCODING_NAME);
+            final byte[] strippedEncoding = new byte[this.encoding.length - 1];
+            System.arraycopy(this.encoding, 1, strippedEncoding, 0, strippedEncoding.length);
+            return PolyLine.wkb(strippedEncoding).toWkt();
         }
-        catch (final Exception e)
+        else
         {
-            throw new CoreException("Could not stringify byte array.", e);
+            try
+            {
+                return new String(this.encoding, ENCODING_NAME);
+            }
+            catch (final Exception e)
+            {
+                throw new CoreException("Could not stringify byte array.", e);
+            }
         }
     }
 
@@ -152,6 +185,7 @@ private String compress(final PolyLine points, final int precision0)
             final long deltaLongitude = longitude - oldLongitude;
             if (Math.abs(deltaLongitude) > MAXIMUM_DELTA_LONGITUDE)
             {
+                logger.warn("Unable to use string compression for {}", points.toWkt());
                 throw new PolyLineCompressionException(
                         "Unable to compress the polyLine, two consecutive points ({} and {}) are too far apart in longitude: {} degrees.",
                         last, location, deltaLongitude / precision);
@@ -182,4 +216,13 @@ private String encodeNumber(final long number0)
         encoded += String.valueOf(Character.toChars((int) number + ENCODING_OFFSET_MINUS_ONE));
         return encoded;
     }
+
+    private byte[] getWkbFallback(final PolyLine polyLine)
+    {
+        final byte[] wkbEncoding = polyLine.toWkb();
+        final byte[] finalEncoding = new byte[1 + wkbEncoding.length];
+        finalEncoding[0] = WKB_SENTINEL;
+        System.arraycopy(wkbEncoding, 0, finalEncoding, 1, wkbEncoding.length);
+        return finalEncoding;
+    }
 }
diff --git a/src/test/java/org/openstreetmap/atlas/geography/StringCompressedPolyLineTest.java b/src/test/java/org/openstreetmap/atlas/geography/StringCompressedPolyLineTest.java
@@ -2,7 +2,6 @@
 
 import org.junit.Assert;
 import org.junit.Test;
-import org.openstreetmap.atlas.geography.StringCompressedPolyLine.PolyLineCompressionException;
 import org.openstreetmap.atlas.utilities.scalars.Distance;
 
 /**
@@ -24,39 +23,26 @@ public void testCompressionDecompression()
         Assert.assertEquals(polyLine, decompressed);
     }
 
-    @Test(expected = PolyLineCompressionException.class)
-    public void testCompressionError1()
-    {
-        final Location location1 = new Location(Latitude.degrees(45.0), Longitude.degrees(-179.0));
-        final Location location2 = new Location(Latitude.degrees(45.0), Longitude.degrees(179.0));
-        final PolyLine line = new PolyLine(location1, location2);
-        final StringCompressedPolyLine compressedLine = new StringCompressedPolyLine(line);
-    }
-
-    @Test(expected = PolyLineCompressionException.class)
-    public void testCompressionError2()
-    {
-        final Location location1 = new Location(Latitude.degrees(45.0), Longitude.degrees(179.0));
-        final Location location2 = new Location(Latitude.degrees(45.0), Longitude.degrees(-179.0));
-        final PolyLine line = new PolyLine(location1, location2);
-        final StringCompressedPolyLine compressedLine = new StringCompressedPolyLine(line);
-    }
-
     /**
-     * Here the delta longitude between loc2 and loc3 is more than 180 degrees, hence the
-     * compression exception.
+     * Here the delta longitude between loc1/loc2 and loc3/loc4 is more than 180 degrees, so the
+     * algorithm falls back on WKB.
      */
-    @Test(expected = PolyLineCompressionException.class)
-    public void testJumpyPolyLine()
+    @Test
+    public void testCompressionWkbFallback()
     {
-        final Location loc1 = Location.forString("5.972761,-75.8373644");
-        final Location loc2 = Location.forString("5.9712693,-75.8363875");
-        final Location loc3 = Location.forString("18.6398595,157.7635783");
-        final Location loc4 = Location.forString("15.3405183,13.9936102");
-        final PolyLine polyLine = new PolyLine(loc1, loc2, loc3, loc4);
+        final Location location1 = new Location(Latitude.degrees(45.0), Longitude.degrees(-179.0));
+        final Location location2 = new Location(Latitude.degrees(45.0), Longitude.degrees(179.0));
+        final Location location3 = new Location(Latitude.degrees(45.0), Longitude.degrees(179.0));
+        final Location location4 = new Location(Latitude.degrees(45.0), Longitude.degrees(-179.0));
+        final PolyLine line1 = new PolyLine(location1, location2);
+        final PolyLine line2 = new PolyLine(location3, location4);
+        final StringCompressedPolyLine compressedLine1 = new StringCompressedPolyLine(line1);
+        final StringCompressedPolyLine compressedLine2 = new StringCompressedPolyLine(line2);
 
-        System.out.println(polyLine);
-        new StringCompressedPolyLine(polyLine);
+        // the toString method should return WKT since the compression is WKB instead of MapQuest
+        // string compression
+        Assert.assertEquals(compressedLine1.toString(), compressedLine1.asPolyLine().toWkt());
+        Assert.assertEquals(compressedLine2.toString(), compressedLine2.asPolyLine().toWkt());
     }
 
     @Test