15

所以我在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);

结果似乎是正确的。如果以顺时针方向跟踪顶点，它将显示正结果，但是如果我以逆时针方向跟踪顶点，它将变为负值。为什么呢？

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

4

5 回答 5

19

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

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);
}
于 2015-11-12T11:44:44.150 回答
17

想象一下从每个顶点到 Y 轴绘制水平线；对于每条边，这将描述一个梯形：

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

内部循环中的公式(X[j]+X[i]) * (Y[j]-Y[i])计算该梯形 if 的面积的两倍Y[i] <= Y[j]，或者是面积的两倍if 的负数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

尽管上面的例子使用了一个凸多边形，这个面积计算对于任意多边形都是正确的，不管它们可能有多少上行和下行路径。

于 2013-04-29T20:45:21.523 回答
1

这背后没有魔法。看看矩阵的行列式（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)会自行取消。所以这是棘手的部分。
于 2013-04-29T17:59:54.027 回答
1

这是使用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();
}

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>

于 2021-02-04T21:04:58.170 回答
0

它在每个定向段 P[i],P[i+1] 和 Y 轴之间累积有符号区域。在循环结束时，多边形外部的区域被抵消（它将用不同的符号计算两次），内部的一个有符号区域仍然存在。

于 2013-04-29T18:05:00.587 回答