有没有什么著名的算法，可以把用户的图纸变成平滑的形状？

Question

我的要求是一个用户应该能够用手画一些东西，然后在他拿下笔（或手指）后，一个算法将其平滑化，并转化成一些基本的形状。然后在他拿下笔（或手指）后，一个算法将其平滑化并转化为一些基本形状。

首先，我想把一张图画转化成一个尽可能与原图相似的矩形。(当然，如果用户故意画了别的东西，这是不可能的。)现在我正在计算一个平均的x和y位置，我正在区分水平线和垂直线。但它还不是一个矩形，而是某种正交线。

我想知道有没有什么知名的算法，因为我在一些触摸屏应用上看到过几次。你有什么阅读技巧吗？

更新：也许模式识别算法能帮到我。有一些手机会要求用户画一个图案来解锁它的按键。

P.S.：我想这个问题与某一门编程语言无关，但如果你有兴趣的话，我会用RaphaelGWT建立一个网络应用。

Answer 1

我的需求：一个用户应该能够用手画出一些东西，然后在他脱下笔（或手指）后，一个算法将其平滑化并转换为一些基本形状。Douglas-Peucker 算法被用于地理学（例如简化GPS轨迹），我想它也可以用在这里。

Answer 2

根据你的描述，我猜你要找的是一个关于 矢量化算法. 这里有一些指针，可能会帮助你。

• https:/en.wikipedia.orgwikiImage_tracing
• http:/outliner.codeplex.com。 - 开源的栅格图片边缘矢量化器。
• http:/code.google.compshapelogicwikivectorization。 - 描述不同的矢量化算法实现
• http:/cardhouse.comcomputervector.htm。

关于矢量化算法的资源很多，我相信你一定能找到适合你的资源。不过我不知道这些算法的实现有多复杂。