如何计算二维多边形的面积？

Question

假设2d空间中的一系列点不是自相交的，那么确定结果多边形面积的有效方法是什么？作为旁注，这不是作业，我不是在寻找代码。我正在寻找一个可以用来实现我自己的方法的描述。我有关于从点列表中拉出一系列三角形的想法，但我知道有一些关于凸多边形和凹多边形的边缘情况我可能无法捕捉到。

Answer 1

交叉产品是经典之作。

如果您要进行大量此类计算，请尝试以下需要减少一半乘法的优化版本：

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;