I am trying to implement the reduction algorithim from https://github.com/hgoebl/simplify-java
I have looked through his test code and tried to come up with what I think is the right logic.
I am taking a list of Location objects, converting them to a Point, running the reduction algorithm, then converting the reduced points back into a list of Location objects.
The problem is here:
float[][] simplified = simplify.simplify(points2D, 10000.0f, true);
It always comes out with a size of 2. Clearly I am doing something wrong but I am not sure what. Can you identify what is wrong with my implementation?
Approach #1 failing
public static ArrayList<Location> reducePath(List<Location> allLocations, double tolerance)
{
// All the points in rows, with columns latitude and longitude
float[][] points2D = new float[allLocations.size()][2];
// Convert Location to Point
int i = 0;
for (Location loc:allLocations)
{
points2D[i][0] = (float)loc.getLatitude();
points2D[i][1] = (float)loc.getLongitude();
i++;
}
PointExtractor<float[]> pointExtractor = new PointExtractor<float[]>()
{
@Override
public double getX(float[] point)
{
return point[0];
}
@Override
public double getY(float[] point)
{
return point[1];
}
};
Timber.tag("Thin").d("2D array size " + points2D.length);
// This is required for the Simplify initalization
// An empty array is explicity required by the Simplify library
Simplify<float[]> simplify = new Simplify<float[]>(new float[0][0], pointExtractor);
float[][] simplified = simplify.simplify(points2D, 10000.0f, true);
Timber.tag("Thin").d("Simplified with size " + simplified.length);
ArrayList<Location> reducedPoints = new ArrayList<>();
// Convert points back to location
for(float[] point:simplified)
{
Location loc = new Location("");
loc.setLatitude(point[0]);
loc.setLongitude(point[1]);
reducedPoints.add(loc);
}
return reducedPoints;
}
Approach #2 also fails I have tried this approach as well:
public static ArrayList<Location> reducePath(List<Location> allLocations, double tolerance)
{
// All the points in rows, with columns latitude and longitude
float[][] points2D = new float[allLocations.size()][2];
// This is required for the Simplify initalization
// An empty array is explicity required by the Simplify library
Simplify<MyPoint> simplify = new Simplify<MyPoint>(new MyPoint[0]);
MyPoint[] allpoints = new MyPoint[allLocations.size()];
// Convert Location to Point
int i = 0;
for (Location loc:allLocations)
{
points2D[i][0] = (float)loc.getLatitude();
points2D[i][1] = (float)loc.getLongitude();
MyPoint p = new MyPoint(loc.getLatitude(), (float)loc.getLongitude());
allpoints[i] = p;
i++;
}
Timber.tag("Thin").d("All points array size " + allpoints.length);
MyPoint[] simplified = simplify.simplify(allpoints, 1.0, false);
Timber.tag("Thin").d("Simplified with size " + simplified.length);
ArrayList<Location> reducedPoints = new ArrayList<>();
// Convert points back to location
for(MyPoint point:simplified)
{
Location loc = new Location("");
loc.setLatitude(point.getX());
loc.setLongitude(point.getY());
reducedPoints.add(loc);
}
return reducedPoints;
}
private static class MyPoint implements Point
{
double x;
double y;
private MyPoint(double x, double y)
{
this.x = x;
this.y = y;
}
@Override
public double getX()
{
return x;
}
@Override
public double getY()
{
return y;
}
@Override
public String toString()
{
return "{" + "x=" + x + ", y=" + y + '}';
}
@Override
public boolean equals(Object o)
{
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MyPoint myPoint = (MyPoint) o;
if (Double.compare(myPoint.x, x) != 0) return false;
if (Double.compare(myPoint.y, y) != 0) return false;
return true;
}
}
Both of these hyper reduce my points to just the first and last location.
Any advice is greatly appreciated.
SOLUTION
Thanks to the advice I have a solution that now works perfectly. Here is the final code:
/**
* For use when making LatLng coordiantes whole intergers
* So the comparator can use values >1.
*/
private static int DELTA_SCALAR = 1000000;
/**
* Is used as the threshold for deciding what points are
* removed when using the path reduction. This value
* was found from running many tests and deciding on the
* best value that worked for GPS Paths.
*/
private static float EPSILON_TOLERANCE = 400.0f;
/**
* Reduces number of points while maintaining the path.
* @param allLocations
* @return ArrayList of all important locations
*/
public static ArrayList<Location> reducePath(ArrayList<Location> allLocations)
{
// The values must correspond to a delta > 1. So the scalar brings up the
// decimal values of LatLng positions to be whole numbers. The point extractor
// is used by the Simplify framework to get the X and Y values.
PointExtractor<Location> pointExtractor = new PointExtractor<Location>()
{
@Override
public double getX(Location location)
{
return location.getLatitude() * DELTA_SCALAR;
}
@Override
public double getY(Location location)
{
return location.getLongitude() * DELTA_SCALAR;
}
};
// This is required for the Simplify initalization
// An empty array is explicity required by the Simplify library
Simplify<Location> simplify = new Simplify<Location>(new Location[0], pointExtractor);
Location[] allLocationsArray = new Location[allLocations.size()];
allLocations.toArray(allLocationsArray);
Location[] simplifiedArray = simplify.simplify(allLocationsArray, EPSILON_TOLERANCE, true);
return new ArrayList<Location>(Arrays.asList(simplifiedArray));
}
