Simplify-Java (by hgoebl) Issue With Reduced Points List Always Size 2

Question

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));
}

Answer 1

The documentation of simplify-java should have mentioned that simplification only works with x, y (and z) coordinates having delta-values greater than 1.

Typical GPS coordinates are something like 47.998554556 and the next point has 47.998554599. The difference is far less than 1 and hence the square is near 0. With such values, the algorithm and the tolerance cannot work. The outcome is that all points between first and last are eliminated.

I've updated the README.

The central point of the solution is to shift the latitude, longitude values to a number range so simplification can work effectively. The best option might be to provide a PointExtractor:

private static PointExtractor<LatLng> latLngPointExtractor =
        new PointExtractor<LatLng>() {

    @Override
    public double getX(LatLng point) {
        return point.getLat() * 1000000;
    }

    @Override
    public double getY(LatLng point) {
        return point.getLng() * 1000000;
    }
};

In case of Lat/Lon values, you should experiment with the tolerance value. When converting Lat/Lon by multiplying with 1e6 (often found as lat6, lng6 afterwords), I've experienced best values for tolerance in the range of 5 to 50 (YMMV).

You can find more details in the README and there is also a TestCase with running code. I hope this helps!