Jump to content
  • Advertisement
Sign in to follow this  
racumin

How to determine shape given a set of points as perimeter

This topic is 2562 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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:



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


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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites

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)


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites

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))



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 this post


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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!