計算多邊形區域

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

結果似乎是正確的。如果按順時針方向追蹤頂點，它將顯示正的結果，但如果我以逆時針方向追蹤頂點，它將變爲負值。爲什麼？

該算法如何工作？我真的很想知道它背後的數學解釋是什麼，因爲我仍然很難理解網絡上的解釋。

來源

2013-04-29 Charlie Kee

這很可能是更適合於http://programmers.stackexchange.com/ – 2013-04-29 17:55:17

其實，這個問題將是programmers.se一個糟糕的配合比stackoverflow。 – comingstorm 2013-04-29 20:52:27

如果明顯更多，怎麼能只有'4'點？ – mikemaccana 2015-06-16 09:25:19

想象一下，從每個頂點到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

雖然上述示例使用了凸面多邊形，這個區域的計算對任意多邊形都是正確的，而不管有多少個上下線他們可能有。

來源

2013-04-29 20:45:21 comingstorm

謝謝你。這張圖真的有助於:) – 2013-05-05 14:08:05

這裏沒有魔術。只要有一個看一個矩陣（http://en.wikipedia.org/wiki/Determinant#2.C2.A0.C3.97.C2.A02_matrices）的決定

編輯：

說實話：有這個代碼一些magick：

任何您需要的三角測量。在這裏：我們創建三角形，從(0,0)開始，有(Xi, Yi)和(Xj, Yj)
您計算每個三角形的行列式以獲得：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-29 17:59:54 neo

它累積每個定向段P [i]，P [i + 1]和Y軸之間的符號區域。在循環結束時，多邊形外面的區域將被抵消（它將被計數兩次，並且具有不同的符號），並保留內部的有符號區域。

來源

2013-04-29 18:05:00

有一個算法來計算多邊形面積：

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-12 11:44:44

計算多邊形區域

回答

相關問題