Is there some well-known algorithm which turns use

问题:

My requirements: A user should be able to draw something by hand. Then after he takes off his pen (or finger) an algorithm smooths and transforms it into some basic shapes.

To get started I want to transform a drawing into a rectangle which resembles the original as much as possible. (Naturally this won't work if the user intentionally draws something else.) Right now I'm calculating an average x and y position, and I'm distinguishing between horizontal and vertical lines. But it's not yet a rectangle but some kind of orthogonal lines.

I wondered if there is some well-known algorithm for that, because I saw it a few times at some touchscreen applications. Do you have some reading tip?

Update: Maybe a pattern recognition algorithm would help me. There are some phones which request the user to draw a pattern to unlock it's keys.

P.S.: I think this question is not related to a particular programming language, but if you're interested, I will build a web application with RaphaelGWT.

回答1:

The Douglas-Peucker algorithm is used in geography (to simplify a GPS track for instance) I guess it could be used here as well.

回答2:

Based on your description I guess you're looking for a vectorization algorithm. Here are some pointers that might help you:

• http://en.wikipedia.org/wiki/Vectorization_(image_tracing)
• http://outliner.codeplex.com/ - open source vectorizer of the edges in the raster pictures.
• http://code.google.com/p/shapelogic/wiki/vectorization - describes different vectorization algorithm implementations
• http://cardhouse.com/computer/vector.htm

There are a lot of resources on vectorization algorithms, I'm sure you'll be able to find something that fits your needs. I don't know how complex these algorithms are to implement them, though,