Detecting lines and circles in x/y datasets I'm trying to do some simple gesture recognition. Circles, I'm assuming, will simply be a set of points which are all within some specified distance range from center. Lines on the other hand, I'm not as clear on lines. I guess one would take the equation of lines of interest (horizontal, vertical, and 45 degree diagonal) and see if the ys are close enough to the given xs?
Are these valid and efficient techniques? Is there anything better?'
Many thanks in advance
 A: I did this about 25 years ago (on a VAX 780 in good old fortran). The task was to find circles and straight lines in an image. 
This is a summary of what was done - as will be obvious.
The image was divided into small squares and straight line segments were found by linear least squares. Then, chains of these straight lines were found by looking for where the end of one segment was close to the end of another. For each of these chains, an attempt was made to fit a straight line and a circle (method described later). If the error was small enough, a fit was declared.
For fitting a straight line, a axis-independent method was used that used the distance from each point to the straight line. This was done using the normal form of the equation of the line, which makes it easy to get the distance from a point to the line. For fitting a circle, instead of the direct least squares method, which has to be iterative and messy, a linear method was used that minimized $\sum (r^2 - (x_i-a)^2 - (y_i-b)^2)^2$. To make this linear, $r^2-a^2-b^2$ was replaced by $c$, and then $r$ was gotten from $a$, $b$, and $c$.
This worked quite well.
Further details are left as an exercise for the reader. You can contact me at mjcohen@acm.org for further info.
