5

我正在尝试从https://github.com/hgoebl/simplify-java实现归约算法

我查看了他的测试代码并试图提出我认为正确的逻辑。

我正在获取一个Location对象列表,将它们转换为 a Point,运行归约算法,然后将归约点转换回Location对象列表。

问题在这里:

 float[][] simplified = simplify.simplify(points2D, 10000.0f, true);

它总是以 2 的大小出现。显然我做错了什么,但我不确定是什么。您能确定我的实施有什么问题吗?

方法 #1 失败

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

方法 #2 也失败了 我也尝试过这种方法:

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

    }

这两个超将我的积分减少到第一个和最后一个位置。

任何意见是极大的赞赏。

解决方案

多亏了建议,我有了一个现在可以完美运行的解决方案。这是最终代码:

/**
 * 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));
}
4

1 回答 1

6

simple-java的文档应该提到,简化仅适用于 delta 值大于 1 的 x、y(和 z)坐标。

典型的 GPS 坐标类似于 47.998554556,下一个点为 47.998554599。差远小于 1,因此平方接近 0。使用这样的值,算法和容差将无法工作。结果是第一个和最后一个之间的所有点都被消除了。

我已经更新了自述文件

解决方案的中心点是将纬度、经度值转换为一个数字范围,以便简化可以有效地工作。最好的选择可能是提供一个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;
    }
};

如果是纬度/经度值,您应该尝试使用该tolerance值。通过乘以1e6(通常发现为 lat6、lng6 后缀)转换纬度/经度时,我体验到了 5 到 50 (YMMV) 范围内的最佳容差值。

您可以在 README 中找到更多详细信息,并且还有一个带有运行代码的 TestCase。我希望这有帮助!

于 2015-12-01T09:28:19.050 回答