3 回答

TA貢獻(xiàn)1830條經(jīng)驗 獲得超9個贊
交叉產(chǎn)品是經(jīng)典之作。
如果您要進(jìn)行大量此類計算,請嘗試以下需要減少一半乘法的優(yōu)化版本:
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;
為清晰起見,我使用數(shù)組下標(biāo)。使用指針更有效。雖然好的編譯器會為你做。
假設(shè)多邊形為“閉合”,這意味著您將第一個點復(fù)制為帶有下標(biāo)N的點。它還假設(shè)多邊形具有偶數(shù)個點。如果N不均勻,則附加第一個點的附加副本。
該算法是通過展開和組合經(jīng)典叉積算法的兩個連續(xù)迭代而獲得的。
我不太確定兩種算法在數(shù)值精度方面的比較。我的印象是上述算法優(yōu)于經(jīng)典算法,因為乘法往往會恢復(fù)減法精度的損失。當(dāng)受限制使用浮動時,與GPU一樣,這可以產(chǎn)生顯著差異。
編輯:“三角形和多邊形2D和3D區(qū)域”描述了一種更有效的方法
// "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;
添加回答
舉報