Calculating Polygon Area

Question

So I've gotten this code in javascript to calculate irregular polygon area from the net.

function polygonArea(X, Y, numPoints)  
{    
area = 0;  // Accumulates area in the loop   
j = numPoints-1;  // The last vertex is the 'previous' one to the first

  for (i=0; i<numPoints; i++)
  { area = area +  (X[j]+X[i]) * (Y[j]-Y[i]); 
      j = i;  //j is previous vertex to i
  }   
  return area/2; 
}

var xPts = [3, 3, 2, 2, 3, 3, 6, 6, 9, 9, 4, 4 ];
var yPts = [2, 4, 4, 5, 5, 6, 6, 5, 5, 3, 3, 2];

var a = polygonArea(xPts, yPts, 4); 
alert("Area  = " + a);

The results seems to be correct. if the vertex traced by clock-wise direction, it will shows positive results however it will become negative if i traced vertex in anti clockwise direction. Why is that so?

How does this algorithm work? i really want to know what is the mathematical explanation behind it, because i am still having a hard time to understand the explanation on the net.

Answer 1

There is an algorithm to calculate polygon area:

function calcPolygonArea(vertices) {
    var total = 0;

    for (var i = 0, l = vertices.length; i < l; i++) {
      var addX = vertices[i].x;
      var addY = vertices[i == vertices.length - 1 ? 0 : i + 1].y;
      var subX = vertices[i == vertices.length - 1 ? 0 : i + 1].x;
      var subY = vertices[i].y;

      total += (addX * addY * 0.5);
      total -= (subX * subY * 0.5);
    }

    return Math.abs(total);
}

Answer 2

Imagine drawing horizontal lines from each vertex to the Y axis; for each edge, this will describe a trapezoid:

Y-axis
^
|
|--------o (X[j], Y[j])
|         \
|          \
|           \
|------------o (X[i], Y[i])
|
+----------------------------> X-axis

The formula (X[j]+X[i]) * (Y[j]-Y[i]) in the inner loop computes twice the area of this trapezoid if Y[i] <= Y[j], or negative twice the area if Y[i] >= Y[j].

For a closed polygon, this naturally subtracts the area to the left of the "upgoing" edges from the area to the left of the "downgoing" edges. If the polygon is clockwise, this neatly cuts out the exact (doubled) area of the polygon; if counterclockwise, you get the negative (doubled) area.

To compute the area of a given polygon,

Y-axis
^
|
|        o------o
|        |       \
|        |        \
|        o         \
|         \         o                  
|          \       /
|           \     /
|            \   /
|             \ /
|              o
|
+-------------------------> X-axis

take the downgoing area:

Y-axis
^
|
|--------o------o
|                \
|                 \
|        o         \
|                   o                  
|                  /
|                 /
|                /
|               /
|--------------o
|
+-------------------------> X-axis

minus the upgoing area:

Y-axis
^
|
|--------o      o
|        |
|        |
|        o
|         \         o                  
|          \
|           \
|            \
|             \
|--------------o
|
+-------------------------> X-axis

Although the above example uses a convex polygon, this area computation is correct for arbitrary polygons, regardless of how many up- and down- paths they may have.

Answer 3

Here is a snippet using Andrii Verbytskyi's response:

/* Get area of a polygon/surface */
function area(polygon) {
    let total = 0;
    for (let i = 0; i < polygon.length; i++) {
        const addX = polygon[i][0];
        const addY = polygon[i === polygon.length - 1 ? 0 : i + 1][1];
        const subX = polygon[i === polygon.length - 1 ? 0 : i + 1][0];
        const subY = polygon[i][1];
        total += (addX * addY * 0.5) - (subX * subY * 0.5);
    }
    return Math.abs(total);
}

function drawPolygon(context, polygon, strokeStyle, fillStyle) {
  context.strokeStyle = strokeStyle;
  context.fillStyle = fillStyle;
  context.beginPath();
  context.moveTo(polygon[0][0], polygon[0][1]); //first vertex
  for (var i = 1; i < polygon.length; i++)
    context.lineTo(polygon[i][0], polygon[i][1]);
  context.lineTo(polygon[0][0], polygon[0][1]); //back to start
  context.fill();
  context.stroke();
  context.closePath();
}

const display = function(n) {
  var context = document.getElementById("canvas").getContext("2d");
  context.clearRect(0, 0, 500, 500);
  drawPolygon(context, polygons[n], "#888", "#88f");
  document.querySelector('span').textContent = area(polygons[n]);
};

const polygons = [
    [[100, 100], [100, 300], [300, 400], [400, 250], [300, 0]],
    [[300, 300], [300, 100], [0, 0], [-100, 400]],
    [[50, 150], [200, 50], [350, 150], [350, 250], [250, 320], [200, 250], [150, 350], [100, 250]],
    [[100, 100], [300, 100], [400, 300], [100, 300]]
];

const buttons = document.querySelectorAll("button");
for (let counter = 0; counter < buttons.length; counter++) {
    buttons[counter].addEventListener("click", function(){
      window.onload = display(counter);
   });
}
window.onload = display(0);

<button onclick="display(0)">Polygon 0</button>
<button onclick="display(1)">Polygon 1</button>
<button onclick="display(2)">Polygon 2</button>
<button onclick="display(3)">Polygon 3</button>
Polygon area : <span id='area'></span>
<canvas id='canvas' width='400' height='400'></canvas>

Answer 4

There's no magick behind that. Just have a look at determinant of a matrix (http://en.wikipedia.org/wiki/Determinant#2.C2.A0.C3.97.C2.A02_matrices)

edit:

To be honest: there's some magick in this code:

1. you need any triangulation. Here: we create triangles starting in (0,0) and having (Xi, Yi) and (Xj, Yj)
2. you calculate the determinant for each triangle to get: Xi Yj - Xj Yi. But here someone calculates (X[j]+X[i]) * (Y[j]-Y[i]) = Xj Yj - Xj Yi + Xi Yj - Xi Yi = (Xj Yj - Xi Yi) + (Xi Yj - Xj Yi). But happily if you add all those the part (Xj Yj - Xi Yi) canceles itself. So it is the tricky part.

Answer 5

It accumulates the signed area between each oriented segment P[i],P[i+1] and the Y axis. At the end of the loop, the area outside the polygon cancels out (it will be counted twice with different signs), and a signed area of the inside remains.