寻找封闭多边形的Douglas-Peucker算法的良好起始点

Question

我正在尝试使用道格拉斯-普克算法来减少多边形的顶点数量。这个算法对于线和路径来说效果很好。

我的问题是，我想要优化的多边形是封闭的。当选择两个相邻的随机点进行优化时，除了起点和终点之外都能很好地工作，因为它们是固定的，无法被优化。

有没有一个好方法来选择一个起始点呢？

- Andreas Löw

Answer 1

我在我的 JavaScript 库中做了类似的事情，找到彼此最远的两个点，并使用它们来优化多边形。

这是代码片段，我相信你可以根据你正在使用的任何语言进行修改：

function polygonPeuckerReduce(path, tolerance) {
    var points = [];
    if (path.length < 3) {
        return points.concat(path);
    } else {
        var widest = 0.0, startIndex = 0;
        // find the widest part of the polygon (only start index is necessary)
        for (var i = 0, l = path.length; i < l; i++) {
            var point = path[i];
            for (var j = i + 1; j < l; j++) {
                var distance = point.distanceTo(path[j]);
                if (distance > widest) {
                    startIndex = i;
                    widest = distance;
                }
            }
        }

        // re-order the points with the new starting point (faster method)
        points = path.splice(startIndex, path.length).concat(path);

        return PEUCKER_INTERNAL(points, tolerance); // the magic
    }
}

- Alex Lein

Answer 2

另一个可能性是扫描所有三个连续顶点集，并选择距离它们的前任和后继顶点相连线最远的两个顶点，即选择原始数据集中两个最大角的顶点。固定这两个顶点，然后对介于顶点之间的顶点应用Douglas-Peucker算法。

如果您的所有点都很接近，则可能会产生噪声。在这种情况下，您可以从每个输入顶点向外两个方向工作，使用Douglas-Peucker算法在每个方向上跳过不必要的顶点。这将导致更大、间隔更广的三元组。再次找到距离前任/后继顶点相连线最远的两个顶点，固定它们，并对介于顶点之间的顶点应用Douglas-Peucker算法。

其他变化也是可能的，但这比其他答案中描述的“随机”或“最远分开”应该给出更好的起点。

- Kekoa

Answer 3

我会随机选择一个点（例如：所有点列表中的“第一个”点），并找到最远的点。这类似于在搜索与线段最远的点时算法的普通步骤。

- Juraj Blaho

---

问题是：如果我有一个由几个边缘顶点组成的矩形形状，它可能会切割边缘 - 使其成为梯形而不是矩形。这也可能导致用5个顶点而不是一个来构建矩形。 - Andreas Löw

@Andreas Löw：这就是Douglas-Peucker算法的问题。它不能保证最优解，而且是贪心算法，不会进行任何回溯。你可以尝试选择所有可能的起点并评估结果。但如果形状保证为矩形，则可能有更好的算法。 - Juraj Blaho

Answer 4

我可能完全误解了这个问题，但听起来你只是想将Douglas-Peucker算法（http://en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm）应用于多边形。唯一的原因是你不能将你的多边形视为起点和终点相同的线，因为该算法要求这两个点不同。

所以我建议在你的多边形上选择两个远离的任意点，然后运行两次Douglas-Peucker算法，一次是顺时针连接你的点之间的路径，一次是逆时针连接你的点之间的路径。

你的任意点保证会出现在最终的解决方案中，但除此之外，它就像是该算法的线性近似。

如果这还不够，请搜索LOD或细节级别，因为这个问题通常在计算机图形学中被称为这个名字，尽管你可能会遇到一堆关于解决具有相当复杂树结构的多面体问题的页面，这可能或可能不是你正在寻找的。

- dhakim