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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search