algorithm - 如何找到手绘多边形的边和顶点

Question

我想制作一个形状识别程序，可以跟踪鼠标并每 1/2 秒记录一次鼠标的位置。我怎样才能使用这些点来找到一个粗糙的多边形？换句话说，如果你只是画一个类似三角形或正方形的形状，它很可能是 50-100 边形，我怎样才能简化它以获得我想要绘制的形状？我知道你可以做一个遗传算法，但不知道它是如何工作的，我想知道任何替代方案。

编辑：凸包不起作用，需要保留凹面。

Answer 1

我会试一试。

1. 让我们在鼠标点击事件发生点开始时调用位置
2. 每个间隔采取另一个称为CURR的位置
3. 让我们调用以前的 CURR，PREV
4. 计算 CURR 和 PREV 之间的斜率 (delta y/delta x)，
5. 计算 CURR 和 START 之间的线的斜率
6. 为两个斜率之间的差异定义一些阈值
7. 如果斜率超过阈值，
   1. 将 START 和 CURR 之间的线存储为 SIDE
   2. 将 CURR 定义为新的 START
8. 重复直到 CURR 在原始 START 的某个半径内或穿过前面的一侧

您也许可以通过计算边数来确定形状。

Answer 2

对于沿 100 边形的每个点，找到由该点和两侧的点形成的小三角形的面积。删除创建最小三角形的点。重复直到最小的三角形大于某个阈值。