Article Preview

COLUMN

Polygon area

Determining the area of a polygon

Issue: 3.5 (May/June 2005)
Author: Thomas Reed
Author Bio: Thomas Reed has been programming as a hobbyist for more than 20 years, and fell in love with the Mac in 1984.
Article Description: No description available.
Article Length (in bytes): 10,606
Starting Page Number: 34
Article Number: 3515
Resource File(s):

3515.zip Updated: 2013-03-11 19:07:58

Related Link(s): None

Excerpt of article text...

Last issue, we talked about how to determine whether a point lies within an arbitrary polygon. To continue on the polygon theme, and thanks to a recent question on the REALbasic Network Users Group mailing list that got me thinking, this time I'd like to discuss finding the area of a polygon. We all know that the formula for the area of a square is width times height. A right triangle would be half of that (taking the sides that meet at the right angle as the width and height). A circle is pi times the radius squared. Okay, those are easy! But what about an arbitrary polygon with any number of straight sides, connected at any angles?

At first glance, this seems like it would be an extremely complex task. Visually, we can break down a polygon into triangles, rectangles, and other regular shapes and get an estimate, or sometimes even a precise value, for the area. Consider the example in Figure 1. A human might visually "cut" the polygon into two triangles, rearrange them into a square, and announce that the area is 100. A computer, however, lacking our intuitive powers, cannot perform this task as easily. So how do we write a program to determine the area of this shape?

I asked a very similar question in the last issue, and the answer was astoundingly simple, requiring a bare minimum of geometry to understand. In this case, the answer is also simple. However, it will challenge your math skills a little more!

Let's start by looking at one method for finding the area of an arbitrary triangle. You may remember the method you learned in trigonometry for finding triangle areas using two sides and the sine of the angle between. Yuck! Who wants to mess with things like a sine function? We'd much prefer to keep this to simple arithmetic operators, right?

Fortunately, there is another way to find the area. Consider Figure 2, where we have defined a triangle using two vectors, which we will call v and w. It is a less commonly-known fact that the area of a triangle is also equal to half of the cross product of v and w.

I can hear those of you without a strong math background saying "The what product?" The cross product is one type of vector multiplication, and the result of this operation is a new vector perpendicular to the plane in which the other two vectors lie. This property can be very useful in other applications, but more important for our purposes is the fact that the length of this new vector is equal to twice the area of the triangle defined by the original vectors.

...End of Excerpt. Please purchase the magazine to read the full article.