Simple shape recognition
-
I'm looking for some code that determines from a series of 2D points, whether the points draw a: - ellipse - line - rect - polygon if none of the above then just a assume a free form polyline. If the function determines a ellipse, line or rect, then return a rect for the bounds. Doesn't have to be super accurate, as it's for a demo program.
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
-
I'm looking for some code that determines from a series of 2D points, whether the points draw a: - ellipse - line - rect - polygon if none of the above then just a assume a free form polyline. If the function determines a ellipse, line or rect, then return a rect for the bounds. Doesn't have to be super accurate, as it's for a demo program.
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
Assuming the ellipse, rectangle and line will be made from points ordered uniformly around their 'perimeter'... If they represent... 1) An ellipse: the distances from the geometric centre to each point will be linearly distributed... ie: the average distance from the centre should be within an epsilon amount to half way between the maximum and minimum distances. 2) A line: take any two points and calculate the 'linear line equation' y=mx+c... then see if all other points fit the equation. 3) A rectangle: the points would fit into four 'linear line equations', one for each side; find a pair of points that at least one other points fits into, repeat with the remaining points until four sides have been found and there are no points left. (This is the hardest of the three... there may be a better way). 4) A polygon... if none of the other conditions apply. Calculating the bounding rectangle is simple... look for maximum/minimum points in both the vertical/horizontal directions. I believe I've done something like this before... I'll see if I can find some code. Hope this helps.
Matthew Butler
-
Assuming the ellipse, rectangle and line will be made from points ordered uniformly around their 'perimeter'... If they represent... 1) An ellipse: the distances from the geometric centre to each point will be linearly distributed... ie: the average distance from the centre should be within an epsilon amount to half way between the maximum and minimum distances. 2) A line: take any two points and calculate the 'linear line equation' y=mx+c... then see if all other points fit the equation. 3) A rectangle: the points would fit into four 'linear line equations', one for each side; find a pair of points that at least one other points fits into, repeat with the remaining points until four sides have been found and there are no points left. (This is the hardest of the three... there may be a better way). 4) A polygon... if none of the other conditions apply. Calculating the bounding rectangle is simple... look for maximum/minimum points in both the vertical/horizontal directions. I believe I've done something like this before... I'll see if I can find some code. Hope this helps.
Matthew Butler
Matthew Butler wrote:
points ordered uniformly
I don't think you could assume this. The points would be collected while the user drags the mouse with the main button help down. So some of the points will be "closer" to each other than others because the speed at which the user moves the mouse will probably not be very even. Thanks for the other suggestions though!
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
-
Matthew Butler wrote:
points ordered uniformly
I don't think you could assume this. The points would be collected while the user drags the mouse with the main button help down. So some of the points will be "closer" to each other than others because the speed at which the user moves the mouse will probably not be very even. Thanks for the other suggestions though!
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
To solve the 'random mouse speed' you could only draw the next point when it is a pre-determined distance from the last... however that may not fit in with your design. However a better way may be to look at the angles between successive points... (This is how I did it)... For a line, the angles would be around 180 degrees. For a rectangle, there will be (over a few points), 3 x 90 degree turns, with the rest 180 degrees. (The end point will be in proximity to the first). For an ellipse, the angles will always be either below or above 180 degrees... depending on whether it is drawn clockwise or not. And a polygon will not follow any of the previous patterns. ... self explanitory. I stored each shape's pattern and iterated through them looking for a match... similar to a regex... but geometrically, with an 'accuracy' value. If not accurate enough (<75%), I assumed it to be random. Hope this helps.
Matthew Butler
-
Assuming the ellipse, rectangle and line will be made from points ordered uniformly around their 'perimeter'... If they represent... 1) An ellipse: the distances from the geometric centre to each point will be linearly distributed... ie: the average distance from the centre should be within an epsilon amount to half way between the maximum and minimum distances. 2) A line: take any two points and calculate the 'linear line equation' y=mx+c... then see if all other points fit the equation. 3) A rectangle: the points would fit into four 'linear line equations', one for each side; find a pair of points that at least one other points fits into, repeat with the remaining points until four sides have been found and there are no points left. (This is the hardest of the three... there may be a better way). 4) A polygon... if none of the other conditions apply. Calculating the bounding rectangle is simple... look for maximum/minimum points in both the vertical/horizontal directions. I believe I've done something like this before... I'll see if I can find some code. Hope this helps.
Matthew Butler
The maximum and minimum X Y coordinates will not do for an ellipse, you need to determine the equation for the ellipse and then take the end points of the axes.
-
The maximum and minimum X Y coordinates will not do for an ellipse, you need to determine the equation for the ellipse and then take the end points of the axes.
I was refurring to the maximum and minimum distances between the points and the geometric centre... not the bounds of the ellipse.
......ooooooooooo......
...ooo.....|.....ooo...
..o........m........o..
.o.........|.........o.
.o.........X----M----o.
.o...................o.
..o.................o..
...ooo...........ooo...
......ooooooooooo......m is the 'minimum' radius of the ellipse. M is the 'maximum' radius of the ellipse. If it was an ellipse, the average distance between each point and the centre, X, would be approximately equal to the (M + m) / 2; This was my original idea... I posted my alternative method (my prefured way and the method I actually got running - in a past program) as a different reply. I believe I saw this method a while ago, but I can't remember where.
Matthew Butler
-
I'm looking for some code that determines from a series of 2D points, whether the points draw a: - ellipse - line - rect - polygon if none of the above then just a assume a free form polyline. If the function determines a ellipse, line or rect, then return a rect for the bounds. Doesn't have to be super accurate, as it's for a demo program.
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
In your definition wouldn't an ellipse or a rect be a polygon? so all you want to really know is if a set of points represent a line or a polygon. Hence the simple solution is if the points aren't all collinear then they represent a polygon, otherwise they represent a line or line-segment.
-
I'm looking for some code that determines from a series of 2D points, whether the points draw a: - ellipse - line - rect - polygon if none of the above then just a assume a free form polyline. If the function determines a ellipse, line or rect, then return a rect for the bounds. Doesn't have to be super accurate, as it's for a demo program.
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
You might want to try finding line segments (assuming points are dense), and than base your recognition on the segment. A trick for this is to use Hough Transforms to find significant line segments. [^] Lines end up as local maxima in the Hough space. You can pick the segment with above value above mode, normalize them, and use the number of segments, as well as the segment values, as a discriminator. This does a reasonable job, I used it for OCR back in the 90s. :doh: Now that I think about it,look for mouse gesture recognition articles on CP, I think there are a couple, and it is what you are doing.
Learn to write self marginalizing code! Call 1-888-BAD-CODE ------------------ Silver member by constant and unflinching longevity.
-
To solve the 'random mouse speed' you could only draw the next point when it is a pre-determined distance from the last... however that may not fit in with your design. However a better way may be to look at the angles between successive points... (This is how I did it)... For a line, the angles would be around 180 degrees. For a rectangle, there will be (over a few points), 3 x 90 degree turns, with the rest 180 degrees. (The end point will be in proximity to the first). For an ellipse, the angles will always be either below or above 180 degrees... depending on whether it is drawn clockwise or not. And a polygon will not follow any of the previous patterns. ... self explanitory. I stored each shape's pattern and iterated through them looking for a match... similar to a regex... but geometrically, with an 'accuracy' value. If not accurate enough (<75%), I assumed it to be random. Hope this helps.
Matthew Butler
Matthew Butler wrote:
For an ellipse, the angles will always be either below or above 180 degrees... depending on whether it is drawn clockwise or not
All it takes is a well drawn spiral, and BOOM! :laugh:
Semicolons: The number one seller of ostomy bags world wide. - dan neely
-
Matthew Butler wrote:
For an ellipse, the angles will always be either below or above 180 degrees... depending on whether it is drawn clockwise or not
All it takes is a well drawn spiral, and BOOM! :laugh:
Semicolons: The number one seller of ostomy bags world wide. - dan neely
Oops. So much for testing... I missed that one. -one quick copy and paste later-
// bail out if first point not near to last point if (CalcLength(points[0], points[points.Length - 1]) > maxDev) return false;Checkmate.:cool:Matthew Butler