Simplify-Java (by hgoebl) 减少点列表总是大小为 2 的问题

Question

我正在尝试实现 https://github.com/hgoebl/simplify-java

的缩减算法

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

我正在获取 Location 个对象的列表，将它们转换为 Point、运行缩减算法，然后将缩减的点转换回 [=15] 的列表=] 对象。

问题在这里：

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

    }

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

非常感谢任何建议。

解决方案

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

/**
 * 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

simplify-java 的文档应该提到简化仅适用于增量值大于 1 的 x、y（和 z）坐标。

典型的 GPS 坐标大约是 47.998554556，下一个点是 47.998554599。差异远小于 1，因此平方接近于 0。对于这样的值，算法和公差无法工作。结果是first和last之间的所有点都被淘汰了。

我更新了README。

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

如果是 Lat/Lon 值，您应该尝试使用 tolerance 值。通过乘以 1e6 转换 Lat/Lon 时（后记通常为 lat6、lng6），我体验过 5 到 50 (YMMV) 范围内的最佳公差值。

您可以在 README 中找到更多详细信息，还有一个包含运行代码的测试用例。希望对您有所帮助！

Simplify-Java (by hgoebl) 减少点列表总是大小为 2 的问题

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

java

douglas-peucker