private static void douglasPeuckerReduction(ArrayList<GeoPoint> shape,boolean[] marked,double tolerance,int firstIdx,int lastIdx){
  if (lastIdx <= firstIdx + 1) {
    return;
  }
  double maxDistance=0.0;
  int indexFarthest=0;
  GeoPoint firstPoint=shape.get(firstIdx);
  GeoPoint lastPoint=shape.get(lastIdx);
  for (int idx=firstIdx + 1; idx < lastIdx; idx++) {
    GeoPoint point=shape.get(idx);
    double distance=orthogonalDistance(point,firstPoint,lastPoint);
    if (distance > maxDistance) {
      maxDistance=distance;
      indexFarthest=idx;
    }
  }
  if (maxDistance > tolerance) {
    marked[indexFarthest]=true;
    douglasPeuckerReduction(shape,marked,tolerance,firstIdx,indexFarthest);
    douglasPeuckerReduction(shape,marked,tolerance,indexFarthest,lastIdx);
  }
}

private static void douglasPeuckerReduction ( ArrayList < GeoPoint > shape , boolean [ ] marked , double tolerance , int firstIdx , int lastIdx ) { if ( lastIdx <= firstIdx + 1 ) { return ; } double maxDistance = 0.0 ; int indexFarthest = 0 ; GeoPoint firstPoint = shape . get ( firstIdx ) ; GeoPoint lastPoint = shape . get ( lastIdx ) ; for ( int idx = firstIdx + 1 ; idx < lastIdx ; idx ++ ) { GeoPoint point = shape . get ( idx ) ; double distance = orthogonalDistance ( point , firstPoint , lastPoint ) ; if ( distance > maxDistance ) { maxDistance = distance ; indexFarthest = idx ; } } if ( maxDistance > tolerance ) { marked [ indexFarthest ] = true ; douglasPeuckerReduction ( shape , marked , tolerance , firstIdx , indexFarthest ) ; douglasPeuckerReduction ( shape , marked , tolerance , indexFarthest , lastIdx ) ; } }
reduce the points in shape between the specified first and last index . mark the points to keep in marked [ ]
