Basically, i have a set of points, which read out the user's mouse input (think of a picture drawn in Pictionary). I would like to detect, if these points represent one of certain shapes. Nothing special, a differentiation between circle, straight line and curved line should suffice.
It should cut you some slack, of course, since you cannot draw a perfect circle with the mouse, and it should approximate the closest exact shape.
Attached some pictures to clarify this.
What I have tried so far is checking the angle of the points to each other to check for a line (which malfunctions, if you backtrack on the line just a little), checking the distance from start to end for a circle (which malfunctions, if you paint just a little too far, also it doesn't really care about the shape this way)
The first thing I thought of when I read this was to use some kind of filter. I learned some about this in Stanford's online AI course. There's 3 lectures availble here. (Computer Vision I-III)
For example, you can create an array of angles between each 2 segments, angles[1, n], angles[i] = get_angle(points[i], points[i - 1]) - get_angle(points[i + 1], points[i])
Then to create an array of the differencies between each angle and the previous one, d_angles[1, n], d_angles[i] = angles[i] - angles[i-1]
Then you can sum absolute values of all d_angles, s = sum(abs(all d_angles)).
Then you can concede, that normal deviation for a line is, for example, da = 5 degrees a point, and
And then if s < n * da, then it's a line.
And if (s > pi * 2 - k) and (s < pi * 2 + k), where k = 10 degrees (for example), then it's a circle.
If it's not a circle and not a line, we can assume it's a different kind of shape.
P.S. You need to include angle which includes points[n]<->points[1] segment if only the length of this segment significantly less then the lenght of the whole line.
P.P.S. If points[n] realy close to points[1], the sum of d_angles will be close to a multiply of 2 * pi, so every random shape with even amount of self crossings will be declared as a circle.
If you already haven't a idea for the circle I can offer you this:
An oval is bordered by two circles. You can detect two nearby points, increase or decrease the angle by 90 (whether you go clockwise or not) and trying to find a point on the other side of the oval. If you do it for each point theoretically you will find a maximum and a minimum value with the associated points, which should staying nearly in a right angle. The crossing point should be the center for the circle with a diameter of the average of the distance values.
I decided to try making something to do this, when I saw the post.. I save some arrays of points for each shape. Then, for each shape I measure for each point from the users dawing, the distance to the closest point int the shape and sum them up. That is the distance to a shape. The shape with the smallest distance is probably what he was trying to draw.
I tested it, with the shapes circle and line, and it seems to work.
Initializer{shapes[(int)Shape.Circle]=newpoint[16]();for(inti=0;i<16;i++){fixedangle=i*360.0/16.0;shapes[(int)Shape.Circle][i]=Point(Cos(angle),Sin(angle));}shapes[(int)Shape.PositiveLine]=newpoint[16]();for(inti=0;i<16;i++){shapes[(int)Shape.PositiveLine][i]=Point(i/8.0-1,i/8.0-1);}shapes[(int)Shape.NegativeLine]=newpoint[16]();for(inti=0;i<16;i++){shapes[(int)Shape.NegativeLine][i]=Point(i/8.0-1,1-i/8.0);}userPoints=newpoint[0]();}point[]userPoints;TriggerMouseDown{events{TriggerAddEventMouseClicked(MouseDown,c_playerAny,c_mouseButtonLeft,true);}actions{userPoints->Resize(0);TriggerEnable(TrackMouse,true);}}TriggerTrackMouse{events{TriggerAddEventMouseMoved(TrackMouse,c_playerAny);TriggerEnable(TrackMouse,false);}actions{//Might be able to optimize this - you probably dont need that many pointsintlength=userPoints->length;userPoints->Resize(length+1);userPoints[length]=Point(EventMouseMovedPosXUI(),EventMouseMovedPosYUI());}}TriggerMouseUp{events{TriggerAddEventMouseClicked(MouseUp,c_playerAny,c_mouseButtonLeft,false);}actions{TriggerEnable(TrackMouse,false);ClampPoints(userPoints);intbestMatch=-1;fixedbestMatchDist=-1;for(inti=0;i<shapes.length;i++){fixeddist=DistanceTo(i,userPoints);if(bestMatch==-1||dist<bestMatchDist){bestMatch=i;bestMatchDist=dist;}}UIDisplayMessage(PlayerGroupAll(),c_messageAreaSubtitle,"Best match was "+(string)(Shape)bestMatch+" with a distance of "+bestMatchDist+".");UIDisplayMessage(PlayerGroupAll(),c_messageAreaSubtitle,"Distance pr point: "+bestMatchDist/userPoints->length);if(bestMatchDist/userPoints->length>0.04)UIDisplayMessage(PlayerGroupAll(),c_messageAreaSubtitle,"Probably not a match");}}point[][3]shapes;enumShape{Circle,PositiveLine,NegativeLine}fixedDistanceTo(intshape,point[]userPoints){//You will be able to optimize this if the shape points is saved in a specific way, for instance sorted by x or yfixedtotDist=0;for(inti=userPoints->length-1;i>=0;i--){fixedminDist=10;//Since it's clamped, 8 is max distance in calculationsfor(intj=shapes[shape]->length-1;j>=0;j--){fixedx=userPoints[i].x-shapes[shape][j].x;fixedy=userPoints[i].y-shapes[shape][j].y;fixeddist=x*x+y*y;if(dist<minDist)minDist=dist;}totDist+=minDist;}returntotDist;}voidClampPoints(point[]points){//Make points within [-1, 1]fixedmaxX=points[0].x;fixedmaxY=points[0].y;fixedminX=maxX;fixedminY=maxY;for(inti=points->length-1;i>0;i--){fixedx=points[i].x;fixedy=points[i].y;if(x<minX)minX=x;if(x>maxX)maxX=x;if(y<minY)minY=y;if(y>maxY)maxY=y;}fixedmidX=(maxX+minX)/2;fixedmidY=(maxY+minY)/2;fixedsizeX=(maxX-minX)/2;fixedsizeY=(maxY-minY)/2;for(inti=points->length-1;i>=0;i--){points[i].x=(points[i].x-midX)/sizeX;points[i].y=(points[i].y-midY)/sizeY;}}enrichpoint{fixedx{get{returnPointGetX(this);}set{this=Point(value,this.y);}}fixedy{get{returnPointGetY(this);}set{this=Point(this.x,value);}}}
I am quite successful with the circle using this approach Mexa linked me. It accounts for most problems, which raised with my previous approaches when detecting circles.
For the line, the angle approach is a little problematic, because everything with just a small nose (shaped like a 1) or a little backtracking involved would show huge angle discrepancies, while still being clearly a line for the most part.
Currently thinking about drawing a linear slope through start and finish and then compare the distance of each point to the line; however I might need a better method than just taking the first and last point... maybe average all points to get a center and average all angles to get an angle... then take min/max values for x and y to limit the line... hmmm
€Beier... for some reason my enrichments for points look exactly like yours :D
Will test yours, but I will try to finish mine ;)
€ Beier, your stuff doesn't seem to work properly. When i draw a horizontal or vertical line, I get sometimes a line, sometimes a circle, sometimes even a division by zero. Also always a Probably not a match message.
Yeah, it won't do horizontal or vertical lines very well due to clamping it to [-1, 1]. But they are rather simple shapes that you can test for before clamping.. There are some room for optimizations and improvements in this code.
Also, the "probably not a match" thingy is just testing if the distance pr point is greater than 0.04, so you can tweak that.. Anyway, you might find better ways of doing it, but there's my go at it :)
Initializer{shapes[(int)Shape.Circle]=newpoint[16]();for(inti=0;i<16;i++){fixedangle=i*360.0/16.0;shapes[(int)Shape.Circle][i]=Point(Cos(angle),Sin(angle));}shapes[(int)Shape.PositiveLine]=newpoint[16]();for(inti=0;i<16;i++){shapes[(int)Shape.PositiveLine][i]=Point(i/8.0-1,i/8.0-1);}shapes[(int)Shape.NegativeLine]=newpoint[16]();for(inti=0;i<16;i++){shapes[(int)Shape.NegativeLine][i]=Point(i/8.0-1,1-i/8.0);}userPoints=newpoint[0]();}point[]userPoints;point[][3]shapes;enumShape{Circle,PositiveLine,NegativeLine}TriggerMouseDown{events{TriggerAddEventMouseClicked(MouseDown,c_playerAny,c_mouseButtonLeft,true);}actions{userPoints->Resize(0);TriggerEnable(TrackMouse,true);}}TriggerTrackMouse{events{TriggerAddEventMouseMoved(TrackMouse,c_playerAny);TriggerEnable(TrackMouse,false);}actions{//Might be able to optimize this - you probably dont need as many pointsintlength=userPoints->length;userPoints->Resize(length+1);userPoints[length]=Point(EventMouseMovedPosXUI(),EventMouseMovedPosYUI());}}TriggerMouseUp{events{TriggerAddEventMouseClicked(MouseUp,c_playerAny,c_mouseButtonLeft,false);}actions{TriggerEnable(TrackMouse,false);if(IsHorizontalLine(userPoints)){UIDisplayMessage(PlayerGroupAll(),c_messageAreaSubtitle,"Horizontal line");return;}if(IsVerticalLine(userPoints)){UIDisplayMessage(PlayerGroupAll(),c_messageAreaSubtitle,"Vertical line");return;}ClampPoints(userPoints);intbestMatch=-1;fixedbestMatchDist=-1;for(inti=0;i<shapes.length;i++){fixeddist=DistanceTo(i,userPoints);if(bestMatch==-1||dist<bestMatchDist){bestMatch=i;bestMatchDist=dist;}}UIDisplayMessage(PlayerGroupAll(),c_messageAreaSubtitle,"Best match was "+(string)(Shape)bestMatch+" with a distance of "+bestMatchDist+".");UIDisplayMessage(PlayerGroupAll(),c_messageAreaSubtitle,"Distance pr point: "+bestMatchDist/userPoints->length);if(bestMatchDist/userPoints->length>0.2)UIDisplayMessage(PlayerGroupAll(),c_messageAreaSubtitle,"Probably not a match");}}boolIsHorizontalLine(point[]points){fixedminY=points[0].y;fixedmaxY=minY;fixedx=points[0].x;intindex=points->length-1;boolpositiveDir=points[index].x>x;intcount=points->length;for(inti=1;i<count;i++){if(x!=points[i].x&&positiveDir!=(x<=points[i].x))returnfalse;x=points[i].x;fixedy=points[i].y;if(y<minY)minY=y;if(y>maxY)maxY=y;if((maxY-minY)>50)returnfalse;}returntrue;}boolIsVerticalLine(point[]points){fixedminX=points[0].x;fixedmaxX=minX;fixedy=points[0].y;intindex=points->length-1;boolpositiveDir=points[index].y>=y;intcount=points->length;for(inti=1;i<count;i++){if(y!=points[i].y&&positiveDir!=(y<=points[i].y))returnfalse;y=points[i].y;fixedx=points[i].x;if(x<minX)minX=x;if(x>maxX)maxX=x;if((maxX-minX)>50)returnfalse;}returntrue;}fixedDistanceTo(intshape,point[]userPoints){//You will be able to optimize this if the shape points is saved in a specific way, for instance sorted by x or y//Also, you can terminate early if you send the current min dist withfixedtotDist=0;for(inti=userPoints->length-1;i>=0;i--){fixedminDist=10;//Since it's clamped, 8 is max distance in calculationsfor(intj=shapes[shape]->length-1;j>=0;j--){fixedx=userPoints[i].x-shapes[shape][j].x;fixedy=userPoints[i].y-shapes[shape][j].y;fixeddist=x*x+y*y;if(dist<minDist*minDist)minDist=SquareRoot(dist);}totDist+=minDist;}returntotDist;}voidClampPoints(point[]points){//Make points within [-1, 1]fixedmaxX=points[0].x;fixedmaxY=points[0].y;fixedminX=maxX;fixedminY=maxY;for(inti=points->length-1;i>0;i--){fixedx=points[i].x;fixedy=points[i].y;if(x<minX)minX=x;if(x>maxX)maxX=x;if(y<minY)minY=y;if(y>maxY)maxY=y;}fixedmidX=(maxX+minX)/2;fixedmidY=(maxY+minY)/2;fixedsizeX=(maxX-minX)/2;fixedsizeY=(maxY-minY)/2;for(inti=points->length-1;i>=0;i--){points[i].x=(points[i].x-midX)/sizeX;points[i].y=(points[i].y-midY)/sizeY;}}enrichpoint{fixedx{get{returnPointGetX(this);}set{this=Point(value,this.y);}}fixedy{get{returnPointGetY(this);}set{this=Point(this.x,value);}}}
Hey.
Basically, i have a set of points, which read out the user's mouse input (think of a picture drawn in Pictionary). I would like to detect, if these points represent one of certain shapes. Nothing special, a differentiation between circle, straight line and curved line should suffice.
It should cut you some slack, of course, since you cannot draw a perfect circle with the mouse, and it should approximate the closest exact shape.
Attached some pictures to clarify this.
What I have tried so far is checking the angle of the points to each other to check for a line (which malfunctions, if you backtrack on the line just a little), checking the distance from start to end for a circle (which malfunctions, if you paint just a little too far, also it doesn't really care about the shape this way)
The first thing I thought of when I read this was to use some kind of filter. I learned some about this in Stanford's online AI course. There's 3 lectures availble here. (Computer Vision I-III)
For example, you can create an array of angles between each 2 segments, angles[1, n], angles[i] = get_angle(points[i], points[i - 1]) - get_angle(points[i + 1], points[i])
Then to create an array of the differencies between each angle and the previous one, d_angles[1, n], d_angles[i] = angles[i] - angles[i-1]
Then you can sum absolute values of all d_angles, s = sum(abs(all d_angles)).
Then you can concede, that normal deviation for a line is, for example, da = 5 degrees a point, and
And then if s < n * da, then it's a line.
And if (s > pi * 2 - k) and (s < pi * 2 + k), where k = 10 degrees (for example), then it's a circle.
If it's not a circle and not a line, we can assume it's a different kind of shape.
P.S. You need to include angle which includes points[n]<->points[1] segment if only the length of this segment significantly less then the lenght of the whole line.
P.P.S. If points[n] realy close to points[1], the sum of d_angles will be close to a multiply of 2 * pi, so every random shape with even amount of self crossings will be declared as a circle.
If you already haven't a idea for the circle I can offer you this:
An oval is bordered by two circles. You can detect two nearby points, increase or decrease the angle by 90 (whether you go clockwise or not) and trying to find a point on the other side of the oval. If you do it for each point theoretically you will find a maximum and a minimum value with the associated points, which should staying nearly in a right angle. The crossing point should be the center for the circle with a diameter of the average of the distance values.
Just playing with ideas here.
I decided to try making something to do this, when I saw the post.. I save some arrays of points for each shape. Then, for each shape I measure for each point from the users dawing, the distance to the closest point int the shape and sum them up. That is the distance to a shape. The shape with the smallest distance is probably what he was trying to draw.
I tested it, with the shapes circle and line, and it seems to work.
I am quite successful with the circle using this approach Mexa linked me. It accounts for most problems, which raised with my previous approaches when detecting circles.
For the line, the angle approach is a little problematic, because everything with just a small nose (shaped like a 1) or a little backtracking involved would show huge angle discrepancies, while still being clearly a line for the most part.
Currently thinking about drawing a linear slope through start and finish and then compare the distance of each point to the line; however I might need a better method than just taking the first and last point... maybe average all points to get a center and average all angles to get an angle... then take min/max values for x and y to limit the line... hmmm
€Beier... for some reason my enrichments for points look exactly like yours :D
Will test yours, but I will try to finish mine ;)
€ Beier, your stuff doesn't seem to work properly. When i draw a horizontal or vertical line, I get sometimes a line, sometimes a circle, sometimes even a division by zero. Also always a Probably not a match message.
Yeah, it won't do horizontal or vertical lines very well due to clamping it to [-1, 1]. But they are rather simple shapes that you can test for before clamping.. There are some room for optimizations and improvements in this code.
Also, the "probably not a match" thingy is just testing if the distance pr point is greater than 0.04, so you can tweak that.. Anyway, you might find better ways of doing it, but there's my go at it :)
Thanks for your help; I think I got it to work like I need it.