计算多边形面积

Question

所以我在javascript中得到了这个代码来从网上计算不规则多边形区域.

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);

结果似乎是正确的.如果通过顺时针方向跟踪顶点,它将显示正结果,但如果我以逆时针方向跟踪顶点,它将变为负数.为什么会这样？

这个算法是如何工作的？我真的想知道它背后的数学解释是什么,因为我仍然很难理解网上的解释.

Answer 1

想象一下从每个顶点到Y轴绘制水平线; 对于每个边缘,这将描述一个梯形:

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

(X[j]+X[i]) * (Y[j]-Y[i])内环中的公式计算此梯形区域的两倍,如果是Y[i] <= Y[j],则为负区域的两倍Y[i] >= Y[j].

对于闭合多边形,这自然地从"下行"边缘的区域中减去"上行"边缘左侧的区域.如果多边形是顺时针方向,则可以整齐地切出多边形的精确(加倍)区域; 如果逆时针,你得到负(加倍)区域.

要计算给定多边形的面积,

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

采取下行区域:

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

减去上行区域:

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

虽然上面的示例使用了凸多边形,但这个区域计算对于任意多边形都是正确的,无论它们可能有多少上行和下行路径.

Answer 2

有一种计算多边形区域的算法:

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);
}