How to find patterns (lines, circles,...) from a list of points?

Question

I have a list of points. Each point being an x and y coordinate (both of which are integers). Now I'm trying to find known patterns, such as lines, arcs or circles, knowing that the points are not perfectly on the pattern.

What's the best way to do it? I don't have many clues to get started.

Edit: the points are ordered. The user is drawing something and the program should detect the best patterns. For instance, if a triangle is drawn, it should detect three lines.

Answer 1

take a look at Hough Transformation. what you do is: you transform your image to "circle" space and then you only have to find light pixels.

finding light pixels in an image is quite easy, just apply a cutoff.

the number of light pixel regions is the number of circles. you can reconstruct their original position on your image by applying the inverse function.

Answer 2

The classic recognizer is a neural network. Neural nets work "okay", and require a training in some fashion.

The mathematical techniques and principles underlying neural nets can be transferred(with appropriate modification) to most other recognizers I've read about; e.g., Markov chains, Bayesian models.

Answer 3

As long as you limit it to basic shapes, you could calculate an averaged 'direction' of the current stroke, and create a sequence of 'strokes' out of these.

It's probably easier to recognize a shape based on that info:

• a circle has a quite constant second derivative
• a 'seven' has a stroke to the right, followed by a stroke to the lower left
• ...

Answer 4

I you look at the distance from some point P to each of the other points, than if P is the center of a circle, you will get some very distinct statistical effects.

You might be able to reverse this and find points that have these properties. As a first pass, something like the standard deviation of the distances might work and to find the location you could take the derivative of that with respect to location and attempt to minimize it. Once you find a minimum, try and find a set of >3 points equidistant from it.

I expect you will need something other than standard deviation, something that is less interested in outliers and more interested in clumping.

Also, this won't do you much good for lines.