Classifying Shape Based on Coordinate Points
Date: 01/03/2000 at 00:35:20 From: Chris Freyer Subject: Determining shape when coordinate points are given I'm trying to design an algorithm to classify shapes. My input is a relatively small set of (x,y) coordinates (fewer than 10,000 points) that describe the boundary of a closed object. My output needs to identify basic shapes (circles, ovals, and polygons, and subtypes where possible - right triangle, square, etc.). Can you point me in the right direction? Chris
Date: 01/03/2000 at 10:52:37 From: Doctor Rob Subject: Re: Determining shape when coordinate points are given Thanks for writing to Ask Dr. Math, Chris. Hmmmmm... Very interesting problem! My first step would be to find the two nearest neighbors of each point. Then I would pick an order, possibly counter-clockwise, for the points, starting with some fixed point and proceeding in that order, returning to the start. Then if one "connects the dots," one should get a diagram of the shape. My next step would be to try to determine whether any set of points contiguous under the above order all lie on a straight line. This would have to be done within a certain tolerance, since your coordinates are undoubtedly decimal values with a certain degree of accuracy (and of inaccuracy). A good way of finding the equation of the best line through a set of points is to use Least Squares Fitting. At the end of this process, you can compute the square root of the average square deviation from the line of best fit, and if this is below some threshold, you could say that the points do lie on that line. Then you can see if you can extend the set of points by including more and more contiguous ones to the original set, and see if they also lie close enough to the line of best fit. At some point, you'll come to a corner, and discover that you cannot add the next point in order. Extending this technique should allow you to handle shapes that are polygonal, giving you the best-fitting equations for the sides, and their intersections giving you the coordinates of the vertices. The distances between adjacent vertices will give you the lengths of the sides, and the interior angles can be computed from the slopes of adjacent sides. Classifying polygonal shapes is done by counting the number of sides, of course. For n >= 5, there are only regular or irregular n-gons. For an irregular one, if all of the interior angles are less than 180 degrees (or pi radians), then it is convex, otherwise concave. For n = 4, there are several possibilities: square, rhombus, parallelogram, kite (convex or concave), trapezoid (isosceles or not), general quadrilateral (convex or concave). For n = 3, there are just a few possibilities: equilateral, isosceles (obtuse, right, or acute), and scalene (obtuse, right or acute) triangles. Then there are shapes that have no line segments as part of their boundaries, that is, whose boundaries are curves. If the equation of the boundary (or a part of it) is a conic, then five points are enough to determine it, and with more points, one again uses Least Squares Fitting to find the conic which best fits. Again, if the square root of the average square deviations from that conic is below some threshold, you would accept that the boundary was that conic. Once you have the conic, you can determine from the equation whether it is a hyperbola, a parabola, or an ellipse. If you have an ellipse, and its major and minor axes are within your tolerance of being equal, you can say that it is a circle. (Alternatively, if the eccentricity is close enough to 0, you can say that it is a circle.) For curves of higher degree, 9 points will determine a cubic, 14 will determine a quartic, and so on. We probably don't have names for the curves you can get this way, although you may find some in the catalog of plane curves at the MacTutor Math History Archive Famous Curves Index http://www-history.mcs.st-and.ac.uk/history/Curves/Curves.html Then there are shapes with some polygonal parts and some curved parts, such as a segment of a circle (which may be a semicircle) or a sector of a circle. Applying the above techniques should allow you to identify the polygonal parts, and then the remaining points can be used to identify the curved parts. The resulting algorithm will be quite complicated when done, but each modular part will be straightforward to understand and, I believe, to program on a computer. If you need more assistance, please write again. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.