Identify shape based on arbitrary number of points

This is a tough one. I'm trying to write code that will identify a shape based on an arbitrary number of points.

Basically, through a touch interface, the user will "d开发者_Python百科raw" a shape (and this is tracked through a certain number of points of touch) and I'm left with a number of points on a 2d surface.

Based on these points, I need to approximate whether the shape outlined is a triangle, a square or a circle. What would be the easiest way to do this? Any ideas?

---

A good first step would be to reduce the number of points to find where the user is trying to draw straight lines - the Ramer–Douglas–Peucker algorithm is appropriate for this.

---

Try finding the curve, triangle, and square that best fit the points with least squares. Whichever shape has the smallest variance/standard-deviation is the likely suspect. Finding the shapes of best fit may be a bit tricky.

Characterize the circle as a center point and a radius. Find the point and radius that minimize the variance. Variance in this case is easy to calculate for a given point and radius. Quick Google search finds a paper titled Finding a Circle that Best Fits a Set of Points with the necessary math.

The square has a center point, side length, and angle of rotation (0 to 90 degrees). Variance is a bit trickier to calculate because you need to either determine the quadrant to find the closest side that distance needs to be minimized to, or calculate distance to all four sides and only keep the smallest. Same principle but you have three variables instead of two.

With the triangles, probably pick three points as the corners and minimize the square of the distance to the sides. Like with the square, you need to figure out which side each point is actually closest to.

I would guess that if you can assume good drawing skills for the users then you can probably just guess a good-enough fit for each shape and check which has the best fit. Circle - center is average of all points and radius is average distance from center. Triangle - take the center as average of all points, furthest point from center is one vertex, furthest point from that vertex is another vertex, and furthest point from the line between them is the third vertex. Square - like triangle, but add one more point, the furthest from the third vertex, to get a general quadrilateral. Not sure how tolerant that approach would be, but could be good enough for your purposes? Either way, it'd probably make good initial guesses for numerical methods to solving the least-squares problems.