# How to determine shape given a set of points as perimeter

## Recommended Posts

racumin    100
Hi,

I am trying to develop a game in android. The user will draw something on the screen (can be a line, circle, triangle or square). Then the program should be able to determine if that drawing was a line, circle, triangle or square.

I already have a solution to determine if the set of points (or the points that was drawn on the screen) is a line. This is my algorithm:

[code]

1. get first and last point of the set
2. create a line using these points
3. for each point in the set compare the distance from the created line
4. if the distance is below a given threshold then the set of pts is a line
[/code]

I have tested this code and it is function as I expected. The problem is, I do not know how to test if the given points is a circle, triangle or square.

Any ideas?

Thanks!

##### Share on other sites
szecs    2990
Maybe you could determine the convex hull of the stuff, then merge nearly collinear lines to one line (like you do it now) then count how many points will remain (2/3/4/more). Then some way (I don't know how....) determine the parameters of the shape.

Well, at first you should definitely clarify for yourself what behavior you want. Draw some test cases in paint and draw the shape you want it to produce. Maybe a problem can't be solved at all for example (well, I do think this particular problem can be solved though)

##### Share on other sites
racumin    100
[quote name='szecs' timestamp='1307688199' post='4821599']
Maybe you could determine the convex hull of the stuff, then merge nearly collinear lines to one line (like you do it now) then count how many points will remain (2/3/4/more). Then some way (I don't know how....) determine the parameters of the shape.

Well, at first you should definitely clarify for yourself what behavior you want. Draw some test cases in paint and draw the shape you want it to produce. Maybe a problem can't be solved at all for example (well, I do think this particular problem can be solved though)
[/quote]

I forgot to say that the set of points was already in sequence. There was no need to perform convex hull algorithm since the set of points was already "sorted". What I want to know is how will I merge the nearly collinear lines to one line. Or in the case of a circle, how will I do it?

I was planning this game on android and I discovered that its API already has a Gestures library. All I need to do was to use the GesturesBuilder application, create any shapes I want, save it to a file and use that file for my game.

##### Share on other sites
owl    376
count the number of lines drawn and sum the angles between them. if they add up to a certain threshold they are some of those shapes

##### Share on other sites
dragongame    538
Have a look at [url="http://en.wikipedia.org/wiki/Hough_transform"]Hough transformation[/url]

##### Share on other sites
szecs    2990
So, is it solved?

Anyhoo, if all you need to determine is the shape type but not some actual enclosing/approximating shape's coordinates, then Owl's method is the most intuitive way.

##### Share on other sites
racumin    100
Half solved I think. But still, Ill take a look at your proposed solutions. Even though there's a gesture API in android, I still want to know how to solve this problem.

Thanks!

##### Share on other sites
D_Tr    362
If I understood correctly, the user will draw a circle and you will get a set of points from the API which are relatively close together. If this is the case, you can find the geometric center of the set of points (by averaging the coordinates). Then you can find the average distance from the center, and the standard deviation of this distance. If the standard deviation is below a threshold you can consider the shape a circle. A less simple solution would be to find the curvature as a function of arc distance along the set of points and use that to detect all the shapes. You can find this crvature radius for each consecutive triad of points by this formula, (off the top of my head):

curvature = (normalized(p3-p2)-normalized(p2-p1)) / (length(p3-p2)+length(p2-p1))

##### Share on other sites
racumin    100
[quote name='D_Tr' timestamp='1307791867' post='4822053']
If I understood correctly, the user will draw a circle and you will get a set of points from the API which are relatively close together. If this is the case, you can find the geometric center of the set of points (by averaging the coordinates). Then you can find the average distance from the center, and the standard deviation of this distance. If the standard deviation is below a threshold you can consider the shape a circle. A less simple solution would be to find the curvature as a function of arc distance along the set of points and use that to detect all the shapes. You can find this crvature radius for each consecutive triad of points by this formula, (off the top of my head):

curvature = (normalized(p3-p2)-normalized(p2-p1)) / (length(p3-p2)+length(p2-p1))
[/quote]

I tried to implement your first solution (avg and standard deviation) and it worked. Problem is, even 'U' shapes and 'C' shapes are considered as circle. This happens when the points in the 'U' or 'C' is still between the avg and standard deviation of the distance from the center.

##### Share on other sites
D_Tr    362
You could check whether the first and last point are close enough to consider the curve closed.

##### Share on other sites
Emergent    982
I don't know how gesture recognition is done on, say, phones. But here's a source of ideas...

In computer vision, there's an algorithm for associating point sets. The idea is that you have a bunch of lists of points,

S[sub]1[/sub] = (s[sub]11[/sub], s[sub]12[/sub], s[sub]13[/sub], ..., s[sub]1n[/sub])
S[sub]2[/sub] = (s[sub]21[/sub], s[sub]22[/sub], s[sub]23[/sub], ..., s[sub]2n[/sub])
...
S[sub]N[/sub] = (s[sub]N1[/sub], s[sub]N2[/sub], s[sub]N3[/sub], ..., s[sub]Nn[/sub])

where each s[sub]ij[/sub] is in [b]R[/b][sup]2[/sup], and each S[sub]i[/sub] is a "formation." Then, you're given some measured list of points,

X = (x[sub]1[/sub], ..., x[sub]N[/sub]).

and you want to find

argmin[sub]j,G,P[/sub] [ (G x[sub]P(1)[/sub] - s[sub]j1[/sub])[sup]2[/sup] + ... + (G x[sub]P(N)[/sub] - s[sub]jN[/sub])[sup]2[/sup] ]

where P is a permutation and G is a transformation (either in SE(2), or any affine transformation, depending on what you want). The goal is to find the optimal 'j,' i.e., the index of the formation that X most closely matches. And you see what's going on here: We're trying to get the data to match each formation as well as possible -- both by translating and rotating it (using the transformation G), and by choosing the correct association between points (the permutation P) -- and then, we pick the formation that we were able to get the data to match best.

This problem is typically solved iteratively, in the following manner:

[i]For each formation j
{
...Initialize G, P
...Do
...{
......Optimize P holding G fixed, using the [url="http://en.wikipedia.org/wiki/Hungarian_algorithm"]Hungarian Algorithm[/url]
......Optimize G holding P fixed; this is a simple least-squares problem in the general affine case and involves the SVD in the SE(2) case.
...} until convergence.
}
Return whichever j gave the lowest value[/i]

Global convergence is not guaranteed, but it works pretty well.

Now, your problem is a little easier, because you don't need to search the entire space of permutations. You know a priori that your points will be in sequence, so you only need to search the space of cyclic shifts, and there are only N of those, not N!. In fact, it may even be that you can assume that the permutation is known, in which case you only have to optimize over G for each j.

Now, how do you do this optimization over G? Let's do the easy case, where you're willing to consider any affine transformation -- not just ones in SE(2). The easiest way to do this is to append a 1 to all your points so you're working in homogeneous coordinates; now you're just looking for a linear transformation that takes one list of points to another in a least squares sense. And this problem is easy. Say you want to find the matrix A that solves

A y[sub]1[/sub] = r[sub]1[/sub]
A y[sub]2[/sub] = r[sub]2[/sub]
...
A y[sub]N[/sub] = r[sub]N[/sub]

in a least-squares sense. This can be rewritten,

A [y[sub]1[/sub],...,y[sub]N[/sub]] = [r[sub]1[/sub],...,r[sub]N[/sub]]

or just

A Y = R

which has solution

A = R pinv(Y)

where pinv(Y) denotes the [url="http://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse"]Moore-Penrose pseudoinverse[/url] of Y.

I hope this gives you some conceptual building blocks you can start to assemble.

##### Share on other sites
racumin    100
Hi all! I found a very good tutorial about gesture recognition [url="http://www.gamedev.net/page/resources/_/reference/programming/sweet-snippets/recognition-of-handwritten-gestures-r2039"]here[/url] It is a very simple solution to my problem.

I really appreciate you help. Thank you very much!