private static void decimate(double tolerance,ArrayList<Location> locations,ArrayList<Location> decimated){
  final int n=locations.size();
  if (n < 1) {
    return;
  }
  int idx;
  int maxIdx=0;
  Stack<int[]> stack=new Stack<int[]>();
  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=LocationUtils.distance(locations.get(idx),locations.get(current[0]),locations.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);
      }
    }
  }
  int i=0;
  idx=0;
  decimated.clear();
  for (  Location l : locations) {
    if (dists[idx] != 0) {
      decimated.add(l);
      i++;
    }
    idx++;
  }
  Log.d(TAG,"Decimating " + n + " points to "+ i+ " w/ tolerance = "+ tolerance);
}

private static void decimate ( double tolerance , ArrayList < Location > locations , ArrayList < Location > decimated ) { final int n = locations . size ( ) ; if ( n < 1 ) { return ; } int idx ; int maxIdx = 0 ; Stack < int [ ] > stack = new Stack < int [ ] > ( ) ; 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 = LocationUtils . distance ( locations . get ( idx ) , locations . get ( current [ 0 ] ) , locations . 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 ) ; } } } int i = 0 ; idx = 0 ; decimated . clear ( ) ; for ( Location l : locations ) { if ( dists [ idx ] != 0 ) { decimated . add ( l ) ; i ++ ; } idx ++ ; } Log . d ( TAG , "Decimating " + n + " points to " + i + " w/ tolerance = " + tolerance ) ; }
decimates the given locations for a given zoom level . this uses a douglas - peucker decimation algorithm .
