canvas - 基于一组连续/半连续点的点/线检测

Question

我正在尝试根据用户在画布上绘制的内容编写一些点/线检测软件（我一直在通过 web 和 html 5 画布进行这一切）。当用户执行 MouseDown 事件时，我们创建一个数组来保存他/她绘图的所有点。之后的每个 MouseMove 事件都会将一个点 (x, y) 推送到数组上。MouseUp 事件表示用户绘图的结束。我想要对这些点做的是确定用户明显改变方向的位置。举个例子：

上述方法产生了以下有序的点集：

[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 4), (7, 3), (8, 2)]

因此，基于这些点，我可以告诉用户在点 (5, 5) 向前明显改变了方向。程序的结果会给我三个点 [(1, 1), (5, 5), (8, 2)] 因为我将使用序列的第一个点，尝试找到一个明显的方向变化并得到该点，并使用序列中的最后一个点。

由于点的数量以及它们完全在一条直线上，因此上面的示例非常简化。当用户实际在画布上绘图时，线条不会完全笔直。出于我的目的，您可以假设用户正在绘制直线而不是明显弯曲的线。

那么根据上述信息，您建议我使用哪些算法、方法等？

编辑：错字

Answer 1

有道格拉斯-普克算法，旨在简化折线和曲线。如果找到具有较少点的相似折线。

Answer 2

Say your points, in order are [(x1, y1), (x2, y2),..., (xn, yn)]. Compute approx derivatives between each consecutive set of points: D1 = (y2-y1)/(x2-x1), D2=(y3-y2)/(x3-x2), etc. Then watch for significant (lasting) changes in the derivative. In your case, D1=1, D2=1, D3=1, D4=1, D5=-1, D6=-1, D7=-1. Note that you have to be careful if they draw a vertical line because the division will be by zero in that case.

Answer 3

假设您有点 P(i)，其中 i=0 ~ (N-1)，对于每个点，您可以将后向斜率计算为 P(i)-P(im)，将前向斜率计算为 P(i+m) -P(i)，其中 m < N。然后您可以计算斜坡在 Pi 处的转角，作为向后斜坡和向前斜坡之间的角度。当转弯角度大于阈值（例如 60 度）时，您的路径会出现急转弯。

m 值的选择有点棘手，需要对您的实际数据点进行一些实验。实际上，它在某种程度上取决于您的数据点的密集程度。如果 m 非常小（例如 1），那么您将从数据噪声中识别出许多不需要的急转弯。当 m 太大时，很可能会错过一些急转弯。当然，通过采用这种方法，我们不会在第一个和最后一个 (m-1) 点中识别出任何急转弯。