@Test public void testSimplify() { final String LINE = "elfjD~a}uNOnFN~Em@fJv@tEMhGDjDe@hG^nF??@lA?n@IvAC`Ay@A{@DwCA{CF_EC{CEi@PBTFDJBJ?V?n@?D@?A@?@?F?F?LAf@?n@@`@@T@~@FpA?fA?p@?r@?vAH`@OR@^ETFJCLD?JA^?J?P?fAC`B@d@?b@A\\@`@Ad@@\\?`@?f@?V?H?DD@DDBBDBD?D?B?B@B@@@B@B@B@D?D?JAF@H@FCLADBDBDCFAN?b@Af@@x@@"; List<LatLng> line = PolyUtil.decode(LINE); assertEquals(95, line.size()); List<LatLng> simplifiedLine; List<LatLng> copy; double tolerance = 5; copy = new ArrayList<>(line); simplifiedLine = PolyUtil.simplify(line, tolerance); assertEquals(20, simplifiedLine.size()); assertEndPoints(line, simplifiedLine); assertSimplifiedPointsFromLine(line, simplifiedLine); assertLineLength(line, simplifiedLine); assertInputUnchanged(line, copy); tolerance = 10; copy = new ArrayList<>(line); simplifiedLine = PolyUtil.simplify(line, tolerance); assertEquals(14, simplifiedLine.size()); assertEndPoints(line, simplifiedLine); assertSimplifiedPointsFromLine(line, simplifiedLine); assertLineLength(line, simplifiedLine); assertInputUnchanged(line, copy); tolerance = 15; copy = new ArrayList<>(line); simplifiedLine = PolyUtil.simplify(line, tolerance); assertEquals(10, simplifiedLine.size()); assertEndPoints(line, simplifiedLine); assertSimplifiedPointsFromLine(line, simplifiedLine); assertLineLength(line, simplifiedLine); assertInputUnchanged(line, copy); tolerance = 20; copy = new ArrayList<>(line); simplifiedLine = PolyUtil.simplify(line, tolerance); assertEquals(8, simplifiedLine.size()); assertEndPoints(line, simplifiedLine); assertSimplifiedPointsFromLine(line, simplifiedLine); assertLineLength(line, simplifiedLine); assertInputUnchanged(line, copy); tolerance = 50; copy = new ArrayList<>(line); simplifiedLine = PolyUtil.simplify(line, tolerance); assertEquals(6, simplifiedLine.size()); assertEndPoints(line, simplifiedLine); assertSimplifiedPointsFromLine(line, simplifiedLine); assertLineLength(line, simplifiedLine); assertInputUnchanged(line, copy); tolerance = 500; copy = new ArrayList<>(line); simplifiedLine = PolyUtil.simplify(line, tolerance); assertEquals(3, simplifiedLine.size()); assertEndPoints(line, simplifiedLine); assertSimplifiedPointsFromLine(line, simplifiedLine); assertLineLength(line, simplifiedLine); assertInputUnchanged(line, copy); tolerance = 1000; copy = new ArrayList<>(line); simplifiedLine = PolyUtil.simplify(line, tolerance); assertEquals(2, simplifiedLine.size()); assertEndPoints(line, simplifiedLine); assertSimplifiedPointsFromLine(line, simplifiedLine); assertLineLength(line, simplifiedLine); assertInputUnchanged(line, copy); ArrayList<LatLng> triangle = new ArrayList<>(); triangle.add(new LatLng(28.06025, -82.41030)); triangle.add(new LatLng(28.06129, -82.40945)); triangle.add(new LatLng(28.06206, -82.40917)); triangle.add(new LatLng(28.06125, -82.40850)); triangle.add(new LatLng(28.06035, -82.40834)); triangle.add(new LatLng(28.06038, -82.40924)); assertFalse(PolyUtil.isClosedPolygon(triangle)); copy = new ArrayList<>(triangle); tolerance = 88; List<LatLng> simplifiedTriangle = PolyUtil.simplify(triangle, tolerance); assertEquals(4, simplifiedTriangle.size()); assertEndPoints(triangle, simplifiedTriangle); assertSimplifiedPointsFromLine(triangle, simplifiedTriangle); assertLineLength(triangle, simplifiedTriangle); assertInputUnchanged(triangle, copy); LatLng p = triangle.get(0); LatLng closePoint = new LatLng(p.latitude, p.longitude); triangle.add(closePoint); assertTrue(PolyUtil.isClosedPolygon(triangle)); copy = new ArrayList<>(triangle); tolerance = 88; simplifiedTriangle = PolyUtil.simplify(triangle, tolerance); assertEquals(4, simplifiedTriangle.size()); assertEndPoints(triangle, simplifiedTriangle); assertSimplifiedPointsFromLine(triangle, simplifiedTriangle); assertLineLength(triangle, simplifiedTriangle); assertInputUnchanged(triangle, copy); final String OVAL_POLYGON = "}wgjDxw_vNuAd@}AN{A]w@_Au@kAUaA?{@Ke@@_@C]D[FULWFOLSNMTOVOXO\\I\\CX?VJXJTDTNXTVVLVJ`@FXA\\AVLZBTATBZ@ZAT?\\?VFT@XGZ"; List<LatLng> oval = PolyUtil.decode(OVAL_POLYGON); assertFalse(PolyUtil.isClosedPolygon(oval)); copy = new ArrayList<>(oval); tolerance = 10; List<LatLng> simplifiedOval = PolyUtil.simplify(oval, tolerance); assertEquals(13, simplifiedOval.size()); assertEndPoints(oval, simplifiedOval); assertSimplifiedPointsFromLine(oval, simplifiedOval); assertLineLength(oval, simplifiedOval); assertInputUnchanged(oval, copy); p = oval.get(0); closePoint = new LatLng(p.latitude, p.longitude); oval.add(closePoint); assertTrue(PolyUtil.isClosedPolygon(oval)); copy = new ArrayList<>(oval); tolerance = 10; simplifiedOval = PolyUtil.simplify(oval, tolerance); assertEquals(13, simplifiedOval.size()); assertEndPoints(oval, simplifiedOval); assertSimplifiedPointsFromLine(oval, simplifiedOval); assertLineLength(oval, simplifiedOval); assertInputUnchanged(oval, copy); }
public static List<LatLng> simplify(List<LatLng> poly, double tolerance) { final int n = poly.size(); if (n < 1) { throw new IllegalArgumentException("Polyline must have at least 1 point"); } if (tolerance <= 0) { throw new IllegalArgumentException("Tolerance must be greater than zero"); } boolean closedPolygon = isClosedPolygon(poly); LatLng lastPoint = null; if (closedPolygon) { final double OFFSET = 0.00000000001; lastPoint = poly.get(poly.size() - 1); poly.remove(poly.size() - 1); poly.add(new LatLng(lastPoint.latitude + OFFSET, lastPoint.longitude + OFFSET)); } int idx; int maxIdx = 0; Stack<int[]> stack = new Stack<>(); double[] dists = new double[n]; dists[0] = 1; dists[n - 1] = 1; double maxDist; double dist = 0.0; int[] current; if (n > 2) { int[] stackVal = new int[]{0, (n - 1)}; stack.push(stackVal); while (stack.size() > 0) { current = stack.pop(); maxDist = 0; for (idx = current[0] + 1; idx < current[1]; ++idx) { dist = distanceToLine(poly.get(idx), poly.get(current[0]), poly.get(current[1])); if (dist > maxDist) { maxDist = dist; maxIdx = idx; } } if (maxDist > tolerance) { dists[maxIdx] = maxDist; int[] stackValCurMax = {current[0], maxIdx}; stack.push(stackValCurMax); int[] stackValMaxCur = {maxIdx, current[1]}; stack.push(stackValMaxCur); } } } if (closedPolygon) { poly.remove(poly.size() - 1); poly.add(lastPoint); } idx = 0; ArrayList<LatLng> simplifiedLine = new ArrayList<>(); for (LatLng l : poly) { if (dists[idx] != 0) { simplifiedLine.add(l); } idx++; } return simplifiedLine; }
PolyUtil { public static List<LatLng> simplify(List<LatLng> poly, double tolerance) { final int n = poly.size(); if (n < 1) { throw new IllegalArgumentException("Polyline must have at least 1 point"); } if (tolerance <= 0) { throw new IllegalArgumentException("Tolerance must be greater than zero"); } boolean closedPolygon = isClosedPolygon(poly); LatLng lastPoint = null; if (closedPolygon) { final double OFFSET = 0.00000000001; lastPoint = poly.get(poly.size() - 1); poly.remove(poly.size() - 1); poly.add(new LatLng(lastPoint.latitude + OFFSET, lastPoint.longitude + OFFSET)); } int idx; int maxIdx = 0; Stack<int[]> stack = new Stack<>(); double[] dists = new double[n]; dists[0] = 1; dists[n - 1] = 1; double maxDist; double dist = 0.0; int[] current; if (n > 2) { int[] stackVal = new int[]{0, (n - 1)}; stack.push(stackVal); while (stack.size() > 0) { current = stack.pop(); maxDist = 0; for (idx = current[0] + 1; idx < current[1]; ++idx) { dist = distanceToLine(poly.get(idx), poly.get(current[0]), poly.get(current[1])); if (dist > maxDist) { maxDist = dist; maxIdx = idx; } } if (maxDist > tolerance) { dists[maxIdx] = maxDist; int[] stackValCurMax = {current[0], maxIdx}; stack.push(stackValCurMax); int[] stackValMaxCur = {maxIdx, current[1]}; stack.push(stackValMaxCur); } } } if (closedPolygon) { poly.remove(poly.size() - 1); poly.add(lastPoint); } idx = 0; ArrayList<LatLng> simplifiedLine = new ArrayList<>(); for (LatLng l : poly) { if (dists[idx] != 0) { simplifiedLine.add(l); } idx++; } return simplifiedLine; } }
PolyUtil { public static List<LatLng> simplify(List<LatLng> poly, double tolerance) { final int n = poly.size(); if (n < 1) { throw new IllegalArgumentException("Polyline must have at least 1 point"); } if (tolerance <= 0) { throw new IllegalArgumentException("Tolerance must be greater than zero"); } boolean closedPolygon = isClosedPolygon(poly); LatLng lastPoint = null; if (closedPolygon) { final double OFFSET = 0.00000000001; lastPoint = poly.get(poly.size() - 1); poly.remove(poly.size() - 1); poly.add(new LatLng(lastPoint.latitude + OFFSET, lastPoint.longitude + OFFSET)); } int idx; int maxIdx = 0; Stack<int[]> stack = new Stack<>(); double[] dists = new double[n]; dists[0] = 1; dists[n - 1] = 1; double maxDist; double dist = 0.0; int[] current; if (n > 2) { int[] stackVal = new int[]{0, (n - 1)}; stack.push(stackVal); while (stack.size() > 0) { current = stack.pop(); maxDist = 0; for (idx = current[0] + 1; idx < current[1]; ++idx) { dist = distanceToLine(poly.get(idx), poly.get(current[0]), poly.get(current[1])); if (dist > maxDist) { maxDist = dist; maxIdx = idx; } } if (maxDist > tolerance) { dists[maxIdx] = maxDist; int[] stackValCurMax = {current[0], maxIdx}; stack.push(stackValCurMax); int[] stackValMaxCur = {maxIdx, current[1]}; stack.push(stackValMaxCur); } } } if (closedPolygon) { poly.remove(poly.size() - 1); poly.add(lastPoint); } idx = 0; ArrayList<LatLng> simplifiedLine = new ArrayList<>(); for (LatLng l : poly) { if (dists[idx] != 0) { simplifiedLine.add(l); } idx++; } return simplifiedLine; } private  PolyUtil(); }
PolyUtil { public static List<LatLng> simplify(List<LatLng> poly, double tolerance) { final int n = poly.size(); if (n < 1) { throw new IllegalArgumentException("Polyline must have at least 1 point"); } if (tolerance <= 0) { throw new IllegalArgumentException("Tolerance must be greater than zero"); } boolean closedPolygon = isClosedPolygon(poly); LatLng lastPoint = null; if (closedPolygon) { final double OFFSET = 0.00000000001; lastPoint = poly.get(poly.size() - 1); poly.remove(poly.size() - 1); poly.add(new LatLng(lastPoint.latitude + OFFSET, lastPoint.longitude + OFFSET)); } int idx; int maxIdx = 0; Stack<int[]> stack = new Stack<>(); double[] dists = new double[n]; dists[0] = 1; dists[n - 1] = 1; double maxDist; double dist = 0.0; int[] current; if (n > 2) { int[] stackVal = new int[]{0, (n - 1)}; stack.push(stackVal); while (stack.size() > 0) { current = stack.pop(); maxDist = 0; for (idx = current[0] + 1; idx < current[1]; ++idx) { dist = distanceToLine(poly.get(idx), poly.get(current[0]), poly.get(current[1])); if (dist > maxDist) { maxDist = dist; maxIdx = idx; } } if (maxDist > tolerance) { dists[maxIdx] = maxDist; int[] stackValCurMax = {current[0], maxIdx}; stack.push(stackValCurMax); int[] stackValMaxCur = {maxIdx, current[1]}; stack.push(stackValMaxCur); } } } if (closedPolygon) { poly.remove(poly.size() - 1); poly.add(lastPoint); } idx = 0; ArrayList<LatLng> simplifiedLine = new ArrayList<>(); for (LatLng l : poly) { if (dists[idx] != 0) { simplifiedLine.add(l); } idx++; } return simplifiedLine; } private  PolyUtil(); static boolean containsLocation(LatLng point, List<LatLng> polygon, boolean geodesic); static boolean containsLocation(double latitude, double longitude, List<LatLng> polygon, boolean geodesic); static boolean isLocationOnEdge(LatLng point, List<LatLng> polygon, boolean geodesic,
                                           double tolerance); static boolean isLocationOnEdge(LatLng point, List<LatLng> polygon, boolean geodesic); static boolean isLocationOnPath(LatLng point, List<LatLng> polyline,
                                           boolean geodesic, double tolerance); static boolean isLocationOnPath(LatLng point, List<LatLng> polyline,
                                           boolean geodesic); static int locationIndexOnPath(LatLng point, List<LatLng> poly,
                                          boolean geodesic, double tolerance); static int locationIndexOnPath(LatLng point, List<LatLng> polyline,
                                          boolean geodesic); static int locationIndexOnEdgeOrPath(LatLng point, List<LatLng> poly, boolean closed,
                                                boolean geodesic, double toleranceEarth); static List<LatLng> simplify(List<LatLng> poly, double tolerance); static boolean isClosedPolygon(List<LatLng> poly); static double distanceToLine(final LatLng p, final LatLng start, final LatLng end); static List<LatLng> decode(final String encodedPath); static String encode(final List<LatLng> path); }
PolyUtil { public static List<LatLng> simplify(List<LatLng> poly, double tolerance) { final int n = poly.size(); if (n < 1) { throw new IllegalArgumentException("Polyline must have at least 1 point"); } if (tolerance <= 0) { throw new IllegalArgumentException("Tolerance must be greater than zero"); } boolean closedPolygon = isClosedPolygon(poly); LatLng lastPoint = null; if (closedPolygon) { final double OFFSET = 0.00000000001; lastPoint = poly.get(poly.size() - 1); poly.remove(poly.size() - 1); poly.add(new LatLng(lastPoint.latitude + OFFSET, lastPoint.longitude + OFFSET)); } int idx; int maxIdx = 0; Stack<int[]> stack = new Stack<>(); double[] dists = new double[n]; dists[0] = 1; dists[n - 1] = 1; double maxDist; double dist = 0.0; int[] current; if (n > 2) { int[] stackVal = new int[]{0, (n - 1)}; stack.push(stackVal); while (stack.size() > 0) { current = stack.pop(); maxDist = 0; for (idx = current[0] + 1; idx < current[1]; ++idx) { dist = distanceToLine(poly.get(idx), poly.get(current[0]), poly.get(current[1])); if (dist > maxDist) { maxDist = dist; maxIdx = idx; } } if (maxDist > tolerance) { dists[maxIdx] = maxDist; int[] stackValCurMax = {current[0], maxIdx}; stack.push(stackValCurMax); int[] stackValMaxCur = {maxIdx, current[1]}; stack.push(stackValMaxCur); } } } if (closedPolygon) { poly.remove(poly.size() - 1); poly.add(lastPoint); } idx = 0; ArrayList<LatLng> simplifiedLine = new ArrayList<>(); for (LatLng l : poly) { if (dists[idx] != 0) { simplifiedLine.add(l); } idx++; } return simplifiedLine; } private  PolyUtil(); static boolean containsLocation(LatLng point, List<LatLng> polygon, boolean geodesic); static boolean containsLocation(double latitude, double longitude, List<LatLng> polygon, boolean geodesic); static boolean isLocationOnEdge(LatLng point, List<LatLng> polygon, boolean geodesic,
                                           double tolerance); static boolean isLocationOnEdge(LatLng point, List<LatLng> polygon, boolean geodesic); static boolean isLocationOnPath(LatLng point, List<LatLng> polyline,
                                           boolean geodesic, double tolerance); static boolean isLocationOnPath(LatLng point, List<LatLng> polyline,
                                           boolean geodesic); static int locationIndexOnPath(LatLng point, List<LatLng> poly,
                                          boolean geodesic, double tolerance); static int locationIndexOnPath(LatLng point, List<LatLng> polyline,
                                          boolean geodesic); static int locationIndexOnEdgeOrPath(LatLng point, List<LatLng> poly, boolean closed,
                                                boolean geodesic, double toleranceEarth); static List<LatLng> simplify(List<LatLng> poly, double tolerance); static boolean isClosedPolygon(List<LatLng> poly); static double distanceToLine(final LatLng p, final LatLng start, final LatLng end); static List<LatLng> decode(final String encodedPath); static String encode(final List<LatLng> path); static final double DEFAULT_TOLERANCE; }