// Publicdomain function by Darel Rex Finley, 2006.

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, selfcrossing 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 selfcrossing, 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 tripleoverlap 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 Yaxis. 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 bottomright and putting it at the topright.) So, the grey
area is easily calculated as (X_{0} + X_{1}) / 2 (the rectangle’s width) * (Y_{0} 
Y_{1}) (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_{0}Y_{1} 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 negativeX space, negativeY 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 rightmost 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). 
Does the brace style in the above code samples freak you out? Click here to see it explained in a new window. 
Quicksort  Point in polygon  Mouseover menus  Gyroscope  Osmosis  Polarizer experiment  Gravity table equilibrium  Calculus without calculus  Overlapping maze 