计算多边形面积

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

结果似乎是正确的。如果按顺时针方向跟踪顶点，它将显示正结果，但如果我按逆时针方向跟踪顶点，则结果将变为负数。为什么会这样？

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

- Charlie Kee

---

这可能更适合发布在 http://programmers.stackexchange.com/ 上。 - Lee Taylor

实际上，这个问题比起 programmers.se 更适合于 stackoverflow。 - comingstorm

当明显有更多的点时，怎么可能只有“4”个点呢？ - mikemaccana

Answer 1

有一种算法可以计算多边形的面积：

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

- Andrii Verbytskyi

Answer 2

想象从每个顶点画一条水平线到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

尽管上面的例子使用了凸多边形，但是该面积计算方法同样适用于任意多边形，无论它们有多少个上下路径。

- comingstorm

Answer 3

这是一个使用Andrii Verbytskyi的回答的片段。

/* 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>

- h0ly

---

什么是面积单位？ - Riaz Ali

Answer 4

这并不神奇，只需要看一下矩阵的行列式 (http://en.wikipedia.org/wiki/Determinant#2.C2.A0.C3.97.C2.A02_matrices)

编辑:

说实话: 这段代码确实有些神奇:

1. 你需要任何一个三角形。这里: 我们从 (0,0) 开始创建三角形，并将其设置为 (Xi, Yi) 和 (Xj, Yj)
2. 你计算每个三角形的行列式以获得: Xi Yj - Xj Yi. 但是这里有人计算了 (X[j]+X[i]) * (Y[j]-Y[i]) = Xj Yj - Xj Yi + Xi Yj - Xi Yi = (Xj Yj - Xi Yi) + (Xi Yj - Xj Yi)。但是幸运的是，如果你把它们全部加起来，部分 (Xj Yj - Xi Yi) 就会相互抵消。所以这是棘手的部分。

- neo

Answer 5

它累积每个有向线段P[i]，P[i+1]与Y轴之间的带符号面积。循环结束时，多边形外部的区域被抵消（它将以不同的符号计算两次），内部的带符号面积保留。

- Eric Bainville