标签: douglas-peucker

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

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

我正在获取Location对象列表，将它们转换为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];
            } …

的道格拉斯-普克线简化算法具有O(N²)的最坏情况下的时间复杂度.然而,对于实际触发这种最坏情况的一条线,两件事必须立即"错误":

• 必须将阈值设置得如此之低以至于保留大多数顶点
• 在每个递归步骤中,与当前端点之间的线偏差最大的顶点必须与其中一个端点接近(就其在线上的索引而言,而不是在其欧氏位置方面).(如果相反,与线的偏差最大的顶点的索引足够接近当前端点之间的中间,则算法应该导致深度的递归二进制细分log(n),从而导致总体时间复杂度O(n log(n)).)

虽然第一个标准很容易触发(只是将公差阈值设置为0.0),但我还没有找到满足第二个标准的线.

那么是否存在导致最坏情况行为的简单示例行(最好是触发明显最坏情况的行为,其中每个递归步骤中具有最高偏差的点直接连接到行的一个端点;但是任何其他示例还好吗？

我有一个路线上的点（纬度，经度）的有序列表。我有一个有序的停靠点列表（经纬度）。假设我有 1000 点和 20 个停靠点。我想将 1000 点减少到 100 点，具体取决于哪些点与路线更相关。例如，像诱导转弯的点。

我认为我可以做到这一点的一种方法是围绕停靠点聚集并随机选择点。但对我来说似乎仍然没有效果。我已经在使用 Douglas Peucker 算法。除了这些还有什么想法？