Polygon Area — Ultra-Easy Algorithm With C Code Sample

Ultra-Easy Polygon Area Algorithm With C Code Sample
©2006 Darel Rex Finley. This complete article, unmodified, may be freely distributed for educational purposes.

So you googled the internet for area-of-polygon algorithms and found only cryptic, greek formulas, or pages telling you to break your polygon up into lots of little triangles? Did it make you want to retch violently and shoot yourself? Ahh...sweet relief...here’s the Frappuccino of which you seek:

//  Public-domain function by Darel Rex Finley, 2006.



double polygonArea(double *X, double *Y, int points) {



  double  area=0. ;

  int     i, j=points-1  ;



  for (i=0; i<points; i++) {

    area+=(X[j]+X[i])*(Y[j]-Y[i]); j=i; }



  return area*.5; }

[Whoa! Since I wrote this page (earlier today), I found that Paul Bourke’s pages include a C function very similar to mine. Even some of the variable names are eerily identical! I swear I didn’t copy it — he and I must be from the same generation of programmers.]

[2010.10.21 — Loop structure improvements by Mikolaj Kaminiski!]

That’s all there is to it! Better than rejuvenation.

This function expects your polygon to be traced clockwise — if it’s traced counterclockwise, the function still works but returns a negative value for the area.

If your polygon crosses itself (i.e. is not “simple” in geometry lingo) then the parts of the polygon that are traced clockwise count as positive area, and the parts that are traced counterclockwise count as negative area. For example, the following, self-crossing polygon has zero area: 1,0, 1,1, 0,0, 0,1

(If you want to calculate the area of the polygon without running into problems like negative area, and overlapping areas described below, you should use the polygon perimeter technique.)

A polygon can be self-crossing, yet still traced entirely clockwise. In that case, the area is all positive, but the overlap area (blue) counts twice. In this example, the area returned would be: grey + 2*blue A triple-overlap would result in tripling of the overlap area, etc.

If the polygon has a “twist,” such that part of the polygon has positive area and part has negative area, and those two areas overlap, then the overlap area cancels out and does not count toward the total area at all — because positive area plus negative area equals no area. In this example, the function returns: grey - red

So how does it work? Consider one side of the polygon. The formula is based on taking the area to the left of the side, all the way to the Y-axis. That area is shaded grey in this illustration.

That area is equal to the area of the grey rectangle in this picture. (You can make the area a rectangle by removing a triangular grey piece from the bottom-right and putting it at the top-right.) So, the grey area is easily calculated as (X₀ + X₁) / 2 (the rectangle’s width) * (Y₀ - Y₁) (the rectangle’s height). This area is what we are adding to the accumulation variable area each time through the loop — but the /2 is moved to the end of the function for purposes of speed.

Going down one side of the polygon adds all the grey area shown here.

Then going up the other side of the polygon substracts all the yellow area shown here, because when a side is going up, Y₀-Y₁ is a negative number. The area that wasn’t subtracted (grey) is the area of the polygon! That’s how it works. And you don’t have to start at the top of the polygon — you can start anywhere, go all the way around, and the numbers will still add up to the same value. (And, contrary to what you may have read on other sites, it doesn’t matter whether some or all of the polygon’s corners are in the negative-X space, negative-Y space, or both — the result is still the same. Try it!)

But what if the polygon is something messy like this? How do we know that it still works?

Draw a horizontal line through every corner of the polygon. This divides the polygon into horizontal strips which are partitioned by straight pieces of the polgyon’s sides.

Now look at just one strip. The right-most segment (red) adds the grey area to the total...

...then the next segment removes the yellow area...

...then the next segment adds the blue area...

...then the next segment removes the yellow area.

Only the grey area (in this illustration) remains in the total, and it’s clearly the polygon’s area (within this strip).

Now of course, our polygonArea() function is not breaking the polygon into strips like this. But since the area to the left of any one side must be equal to the sum of that side’s strip-by-strip pieces, the grand total must be the same, and must be equal to the area of the whole polygon.

Send me an e-mail!

Does the brace style in the above code samples freak you out? Click here to see it explained in a new window.