假設2d空間中的一系列點不是自相交的，那么確定結果多邊形面積的有效方法是什么？作為旁注，這不是作業，我不是在尋找代碼。我正在尋找一個可以用來實現我自己的方法的描述。我有關于從點列表中拉出一系列三角形的想法，但我知道有一些關于凸多邊形和凹多邊形的邊緣情況我可能無法捕捉到。
3 回答
慕標琳琳
TA貢獻1830條經驗 獲得超9個贊
交叉產品是經典之作。
如果您要進行大量此類計算，請嘗試以下需要減少一半乘法的優化版本：
area = 0;
for( i = 0; i < N; i += 2 )
area += x[i+1]*(y[i+2]-y[i]) + y[i+1]*(x[i]-x[i+2]);
area /= 2;
為清晰起見，我使用數組下標。使用指針更有效。雖然好的編譯器會為你做。
假設多邊形為“閉合”，這意味著您將第一個點復制為帶有下標N的點。它還假設多邊形具有偶數個點。如果N不均勻，則附加第一個點的附加副本。
該算法是通過展開和組合經典叉積算法的兩個連續迭代而獲得的。
我不太確定兩種算法在數值精度方面的比較。我的印象是上述算法優于經典算法，因為乘法往往會恢復減法精度的損失。當受限制使用浮動時，與GPU一樣，這可以產生顯著差異。
編輯：“三角形和多邊形2D和3D區域”描述了一種更有效的方法
// "close" polygon
x[N] = x[0];
x[N+1] = x[1];
y[N] = y[0];
y[N+1] = y[1];
// compute area
area = 0;
for( size_t i = 1; i <= N; ++i )
area += x[i]*( y[i+1] - y[i-1] );
area /= 2;
添加回答
舉報
0/150
提交
取消