假設多邊形不會自相交,那麼最有效的方法是什麼?多邊形有N個頂點。 我知道它可以用座標來計算,但是還有其他的一般方法嗎?如何計算非凸多邊形的面積?
回答
解決這個問題的最好辦法就是將多邊形看作幾個三角形,分別找到它們的區域,然後將它們總計爲總面積。所有多邊形,規則的或不規則的,基本上只是一堆三角形(對角線切成四邊形以形成兩個三角形,五角形從一個角落到兩個最相反的三角形,並且模式繼續)。這對代碼很簡單。
一種用於這種通用算法可以被編碼如下:
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
它應該是相對無痛這個適應任何形式的你是存儲在您的座標算法,和任何語言使用的是爲您的項目。
我不認爲你的答案有任何問題。這些都是有梯形的區域,而不是三角形,如果它們重疊,則完全沒問題。如果事實上,如果頂點被存儲爲與限定的橫積運算2D矢量,它甚至可以被簡化總結(V [I]^V [I + 1]) –
@AntonKnyazyev好的謝謝,我刪除該警告。 –
- 從多邊形中取3個連續的點。
- 計算所得三角形的面積。
- 從多邊形中移除3個點的中點。
- 做一個測試,看看移除的點是否在剩餘的多邊形內。如果它在裏面從總數中減去三角形區域,否則添加它。
- 重複,直到多邊形由一個三角形組成,並將該三角形的面積添加到總數。
編輯:解決由@NicolasMiari給出簡單地使兩道次,在第一道次的問題僅處理是內部其餘多邊形,在第二次處理,其餘的頂點。
運行時會爲此做什麼? – rgs
從這個問題:「最有效的方法是什麼?」這個直接的實現至少是O(N^2)。爲什麼所有的答案都給出了一個具有已知的簡單O(N)解決方案的問題的非最優算法?與凸多邊形相比,獲得非凸多邊形區域的難度較大,但最優算法在兩種情況下都是相同的。然而,這個問題和排名靠前的答案會讓任何人都覺得你需要一個複雜的算法來處理非凸情況。這是非常具有誤導性的。 –
@TimothyShields我的算法很直觀,不是你的,但是你的wikipedia鏈接可以幫助你很多。別擔心,奶油會升到最高點。 –
只要您移除的三角形不包含「孔」(多邊形的其他頂點),「一次撕開一隻耳朵」算法就可以工作。
也就是說,你需要選擇下面的綠色三角形,不紅色的:
然而,它始終是可以這樣做(不能證明數學現在,但你必須相信我)。您只需走多邊形的頂點並執行一些包含測試,直到找到合適的三元組。
來源:我曾經根據我在Computational Geometry in C by Joseph O'Rourke中讀到的內容實現了任意非相交多邊形的三角剖分。
的籤面積,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)
這是一個線性時間算法,這是微不足道的並行。還要注意,當頂點的座標都是整數值時,它是一個精確的算法。
這是最好的答案,但你應該展開A()函數。還要注意,不要緊,你在那些一個用什麼P [0]()調用,所以你還不如用(0,0)不變,並保存一些操作 –
@MattTimmermans更新,包括你的建議。 –
非常有趣。如果你所需要的只是知道多邊形的總面積(就像本例中的OP一樣),我猜測執行一個實際的三角測量畢竟是矯枉過正的(儘管一旦你已經完成了從單個三角形計算總面積的計算是很簡單的完成了)。 –
- 1. 從非凸多邊形上的地理座標計算面積
- 2. 計算多邊形的面積
- 3. Android計算多邊形的面積
- 4. 計算多邊形的面積
- 5. 非凸多邊形 - 使用凸包算法的預處理
- 6. 如何計算地球上自相交多邊形的面積
- 7. 如何計算地圖上的多邊形面積?
- 8. 如何計算iOS中多邊形的物理面積?
- 9. 非重疊的非凸多邊形
- 10. 計算多邊形的最小面積矩形
- 11. 計算平面上封閉多邊形的面積
- 12. 凸多邊形,圖形算法
- 13. OpenGL中的輪廓非凸多邊形
- 14. Cuda中的凸多邊形算法?
- 15. Python:多邊形的面積
- 16. WPF多邊形的基本計算:面積和質心
- 17. 在for循環中計算R中多邊形的面積
- 18. R用於計算多邊形的面積和質心
- 19. 計算正多邊形問題的面積
- 20. 計算多邊形的長度和麪積
- 21. 計算複雜(自相交)多邊形的面積
- 22. 使用Python計算緯度/經度多邊形的面積
- 23. 在Java中繪製多邊形並計算面積
- 24. 如何計算多邊形的點數爲Lat長時,MySQL數據庫中的多邊形面積?
- 25. 在scipy中計算兩個不相交多邊形的凸殼
- 26. 如何用Simpson法則使用座標來計算多邊形的面積?
- 27. 如何計算MATLAB中棋盤圖像中的多邊形面積?
- 28. 多邊形C++的凸性?
- 29. 計算凸包邊界
- 30. 計算幾何(多邊形)
除了使用座標? – Beta
讓我向您介紹http://math.stackexchange.com,人們在這裏回答很好的數學問題。 –
@ringø這是一個非常好的編程問題。對於你個人來說什麼都沒有反對,但是那些認爲任何涉及一些數學問題的人都不是編程,實際上是在危害社區。 – Gene