Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
College Euclidean Geometry
High School Euclidean/Plane Geometry

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/