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

Question

我想制作一个形状识别程序，它可以跟踪鼠标并记录每0.5秒的位置。我如何使用这些点找到一个大致的多边形？换句话说，如果你只画一个类似三角形或正方形的形状，它更可能是50-100边形，我该如何简化它以得到我想要的形状？我知道可以使用遗传算法，但不知道具体如何操作，我想了解其他替代方案。

注：凸包无法使用，需要保留凹度。

- invisible bob

Answer 1

我来试试。

1. 我们把鼠标点击下去时的位置称为起点（START）
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在一定半径范围内或穿过以前的任意一条边

你可以通过计算边数来确定形状。

- David Chan

---

我喜欢这个解决方案，但是我只能接受一个答案，而另一个答案更直观一些，所以我会先从它开始。 - invisible bob

在我看来，使用斜率比计算三角形面积更好，因为它是一种更广泛的解决方案，可以丢弃共线点，特别是在处理像素坐标时。 - mavrosxristoforos

Answer 2

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

- Fantius

---

哪个更有效，尺寸还是角度测量？ - invisible bob

对于在[P1，P2，P3 ... PN]中的Pi，如果m∠p（i-1）p（i）p（i+1）>阈值，则删除点。 - invisible bob

我不知道。我猜你得试一下看看。我的猜测是大小会更有效，因为当鼠标移动缓慢且生成的点彼此靠近时，即使它不是预期形状中的真实角度，也可能发生大的角度变化。 - Fantius

但当它移动得更快时，三角形比移动缓慢时要大...我几乎已经让角度运转了，我会尝试两种方法。也许混合使用会效果最好？ - invisible bob

当你说更大时，我必须假设你指的是更长。但它们也应该非常薄。因此，面积仍应该很小。 - Fantius