javascript - 将多边形线拟合到 Canvas 中绘制的像素的算法？

Question

假设我创建 a JS tool允许我在 Canvas 上自由地绘制任何我想要的东西，这样我就可以使用鼠标制作手绘图片，就像这样简单:

是否有一种算法可以用来将一系列折线拟合到这些绘制的像素上？显然，您需要能够选择您想要的准确程度，例如折线可以有 20 个点，也可以有 1000 个点，从而使其非常准确。

另外，我不确定它是如何工作的，因为绘制的“线”的宽度/厚度超过 1px。就像如果你有一个直径为 100px 的大圆，算法如何能够在其中拟合一条“线”。

这种类型的算法是否有特定的名称，用于将点拟合到形状？

Answer 1

与其尝试从像素重新组合折线，不如在用户绘制线条时保存每个鼠标移动位置会更容易。然后这些保存的位置就成为您的折线。

您正在寻找路径简化算法。

我见过的最常见的算法是 Ramer–Douglas–Peucker 算法，该算法消除了偏离理想线太远的“额外”点。

Mike Bostock(AMAZING d3 库的创建者)做了一个很好的例子，展示了消除路径上“额外”点的效果:bost.ocks.org/mike/simplify

如果您使用的是 NodeJS，Vladimir Agafonkin 有一个也适用于 NodeJS 的简化算法:https://github.com/mourner/simplify-js

祝您的项目顺利!