javascript - 寻找闭合路径的多边形近似

Question

我希望能够找到闭合路径的最佳拟合多边形近似（可以是从图像中拉出的任何路径），但是在如何编写算法来找到它时遇到了问题。

我可以想到一种幼稚的方法：沿路径的每 x 个像素，为这些像素选择最佳拟合线，然后针对不同的起始偏移和长度进行蛮力，并找到以最小数量最小化最小二乘误差的那个的行。

必须有更优雅的东西。有人知道吗？另外，（畏缩）但这将在javascript中实现，除非我真的很绝望，所以为你做事的好图书馆几乎被排除在外，（例如，opencv有一个多边形拟合器）。

Answer 1

D3.js 1有一些您可以使用的自适应重采样代码。还有所用算法的图解说明（Visvalingam 算法）。

Answer 2

Ramer-Douglas-Peucker算法在这里似乎很合适，并且易于实现。请注意，可接受的错误是该算法的输入，因此如果您有目标行数，则可以使用错误参数进行二进制搜索以命中目标。