问题标签 [douglas-peucker]

我在各种编程语言中看到了许多使用 Douglas-Peucker 折线简化算法来生成 GPolyline 以在 Google 地图上使用的示例。该算法在表示为平面上的折线时，涉及计算点和线之间的距离（通过另外两个点）。

现在，到目前为止，我看到的所有示例都以非常幼稚的方式应用该算法，只需将 x 和 y 替换为纬度和经度。这可能会产生可接受的结果，只要折线非常局部化，不太靠近极点，并且不穿过 180° 子午线，但我想实现更通用的算法版本。

所以，如果我没记错的话，我需要计算球体表面上最短弧的长度，从一个点到穿过球体表面另外两个点的圆，其中心与球心（地球）。

有谁知道计算这个长度的公式？

提前致谢

我需要获取 n 个点的 2D 图并将其减少 r 个点（其中 r 是小于 n 的特定数字）。例如，我可能有两个总点数略有不同的数据集，比如 1021 和 1001，我想强制两个数据集都有 1000 个点。我知道几个简化算法：Lang Simplification 和 Douglas-Peucker。我在以前的项目中使用过 Lang，但要求略有不同。

我正在寻找的算法的具体属性是：

1) 必须保持线条的形状

2）必须允许我将数据集减少到特定数量的点

3）相对较快

这篇文章讨论了不同算法的优点。我将发布第二条关于 Java 或 Groovy 实现的建议（为什么要重新发明轮子）。

我担心上面的要求 2。我不是这些算法的专家，不知道我是否可以指定输出点的确切数量。我使用的 Lang 的实现将 lookAhead、tolerance 和 Points 数组作为输入，所以我看不到如何规定输出中的点数。这是我当前需求的关键要求。可能是因为我们之前使用过Lang的具体实现，但是我在网上没有看到很多关于Lang的资料。或者，我们可以使用 Douglas-Peucker，但我再次不确定是否可以指定输出中的点数。

我应该补充一点，我不是这些类型的算法或任何类型的数学专家的专家，所以我只是在寻找凡人类型的建议 :) 我如何满足上述要求 1 和 2？我会为正确的解决方案牺牲性能。

这实际上是我们的论文，我们需要使用 Ramer-Douglas-Peucker 算法来简化行，任何人都可以帮助我如何在 Android 应用程序中实现这一点。

我只想知道如何从我绘制的线中获取点串，并通过减少总数来简化线。根据下面给定的代码点？

这是主要课程。

单击现有菜单时，它将简化正在绘制的线并显示具有较少点的线或已简化的线。我打算为它创建一个新类，但我不知道如何从画布中绘制的线中获取点串。

这是我的代码，它被编译为 JAVA 应用程序。我要创建的是一个 Android 应用程序。我只想问我如何将这些代码转换为代码，以便当我将其编译为 ANDROID APPLICATION 时不会产生错误。

有人可以帮我怎么做吗？谢谢

这是我的代码：

我正在努力将旧坐标系的一些地图/区域转换为更简单（不太详细）的模型，以便在网络上表示（使用jVectorMap）。我已成功使用 Douglas Peucker 算法（来自此处的代码：http: //www.codeproject.com/Articles/18936/AC-Implementation-of-Douglas-Peucker-Line-Approxi）。

它工作得很好，但是这个实现没有考虑到这些区域相互对齐（共享边界），这在使用更高的容差时会导致非常丑陋的结果，如下所示。

是否有可能实施区域保持一致的解决方案？

我有一个路线上的点（纬度，经度）的有序列表。我有一个有序的站点列表（纬度，经度）。假设我有 1000 个点和 20 个停止点。我想根据哪些点与路线更相关，将 1000 个点减少到 100 个左右。例如引起转弯的点。

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

Douglas-Peucker 线简化算法的最坏情况时间复杂度为 O(n²)。然而，要让一条线真正触发这种最坏的情况，有两件事必须同时出现“错误”：

• 阈值必须设置得如此之低，以保持大多数顶点
• 在每个递归步骤中，与当前端点之间的线偏差最大的顶点必须靠近（就其在线索引而言，而不是其欧几里德位置而言）到端点之一。（如果相反，与直线偏差最大的顶点的索引足够接近当前端点之间的中间，则该算法应导致深度的递归二进制细分log(n)，从而导致整体时间复杂度为O(n log(n))。）

虽然第一个标准很容易触发（只需将公差阈值设置为 0.0），但我还没有找到满足第二个标准的线。

那么是否有一条导致最坏情况行为的简单示例行（最好是触发明显最坏情况的行，其中每个递归步骤中偏差最大的点直接连接到行的端点之一；但是任何其他示例也很好）？

我研究了 Douglas Peucker 算法。也许我可以用它作为一种替代解决方案，让我的画自由流动。但是我的问题是，当我在绘制的时候，之前绘制的点也在移动。在数组中的同一点集合中绘制时，有什么方法可以使绘制的线静止。

这是代码

目前我正在使用“Douglas Peucker”算法。

我的问题是，当我画画的时候，之前画的线也在变化，这当然不现实。是否有其他替代算法来最小化保存的点但不改变以前的绘制点或其他方式来改变“Douglas Peucker”以满足我的需要？

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

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

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

问题在这里：

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

方法 #1 失败

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

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

任何意见是极大的赞赏。

解决方案

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