如何計算非凸多邊形的面積？

Question

假設多邊形不會自相交，那麼最有效的方法是什麼？多邊形有N個頂點。 我知道它可以用座標來計算，但是還有其他的一般方法嗎？

Answer 1

解決這個問題的最好辦法就是將多邊形看作幾個三角形，分別找到它們的區域，然後將它們總計爲總面積。所有多邊形，規則的或不規則的，基本上只是一堆三角形（對角線切成四邊形以形成兩個三角形，五角形從一個角落到兩個最相反的三角形，並且模式繼續）。這對代碼很簡單。

一種用於這種通用算法可以被編碼如下：

function polygonArea(Xcoords, Ycoords) { 
    numPoints = len(Xcoords) 
    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 + (Xcoords[j]+Xcoords[i]) * (Ycoords[j]-Ycoords[i]); 
     j = i; //j is previous vertex to i 
    } 
    return area/2; 
} 

Xcoords和Ycoords是數組，其中Xcoords存儲X座標，並Ycoords的Y座標。

該算法從以前的頂點迭代構造三角形。

我修改這個從提供Here by Math Open Ref

它應該是相對無痛這個適應任何形式的你是存儲在您的座標算法，和任何語言使用的是爲您的項目。

Answer 2

1. 從多邊形中取3個連續的點。
2. 計算所得三角形的面積。
3. 從多邊形中移除3個點的中點。
4. 做一個測試，看看移除的點是否在剩餘的多邊形內。如果它在裏面從總數中減去三角形區域，否則添加它。
5. 重複，直到多邊形由一個三角形組成，並將該三角形的面積添加到總數。

編輯：解決由@NicolasMiari給出簡單地使兩道次，在第一道次的問題僅處理是內部其餘多邊形，在第二次處理，其餘的頂點。

Answer 3

只要您移除的三角形不包含「孔」（多邊形的其他頂點），「一次撕開一隻耳朵」算法就可以工作。

也就是說，你需要選擇下面的綠色三角形，不紅色的：

然而，它始終是可以這樣做（不能證明數學現在，但你必須相信我）。您只需走多邊形的頂點並執行一些包含測試，直到找到合適的三元組。

來源：我曾經根據我在Computational Geometry in C by Joseph O'Rourke中讀到的內容實現了任意非相交多邊形的三角剖分。

Answer 4

的籤面積，A(T)，三角形T = ((x1, y1), (x2, y2), (x3, y3))的被定義爲以下矩陣的1/2倍的行列式：

|x1 y1 1| 
|x2 y2 1| 
|x3 y3 1| 

行列式是-y1*x2 + x1*y2 + y1*x3 - y2*x3 - x1*y3 + x2*y3。

給定一個多邊形由頂點定義p[0], p[1], ..., p[N - 1]（凸或凹），則可以如下計算多邊形的面積。

area = 0 
for i in [0, N - 2]: 
    area += A((0, 0), p[i], p[i + 1]) 
area += A((0, 0), p[N - 1], p[0]) 
area = abs(area) 

使用對上述的行列式的表達，可以有效地計算A((0, 0), p, q)爲0.5 * (-p.y*q.x + p.x*q.y)。進一步的改進是0.5做乘法只有一次：

area = 0 
for i in [0, N - 2]: 
    area += -p[i].y * p[i+1].x + p[i].x * p[i+1].y 
area += -p[N-1].y * p[0].x + p[N-1].x * p[0].y 
area = 0.5 * abs(area) 

這是一個線性時間算法，這是微不足道的並行。還要注意，當頂點的座標都是整數值時，它是一個精確的算法。

Link to Wikipedia article on this algorithm