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

Question

我正在尝试使用Douglas-Peucker算法来减少多边形的顶点-该算法对直线和路径非常有效。

我的问题是我想要优化的多边形是封闭的。当选择两个随机邻接点时，优化效果很好-除了起点和终点-因为它们是固定的，不能优化。

有没有选择起点的好方法？

Answer 1

我只会随机选择一个点(例如:所有点列表中的“第一个”点)，然后找到最远的点。这与从线段搜索最远的点时算法的普通步骤类似。

Answer 2

我在这里可能完全误解了这个问题，但听起来您只是想将Douglas-Peucker算法(http://en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm)应用于多边形。唯一的原因是，你不能仅仅把多边形看作一条起点和终点相同的直线，因为算法要求你让这两个点是不同的。

所以我建议在多边形上选取两个相距很远的任意点，然后运行Douglas-Peucker算法两次，一次是顺时针方向的点之间的路径，一次是逆时针方向的点之间的路径。

你的任意点肯定会出现在最终的解中，但除此之外，它会尽可能接近算法的线近似。

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

Answer 3

我在我的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
    }
}