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

Question

假设在二维空间中有一系列不相交的点，如何有效地确定形成的多边形的面积？

值得注意的是，这不是作业，我也不在寻找代码。我希望找到一种方法的描述，以便能实现自己的方法。我有一些想法，比如从点集合中获取三角形序列，但是我知道对于凸多边形和凹多边形之类的特殊情况可能会出现问题。

- Jason Z

---

“表面积”这个术语有点误导。你似乎只想要普通的面积。在三维空间中，“表面积”是指外部表面的面积，因此该概念的自然二维推广应该是多边形周长的长度，显然不是你要找的东西。 - batty

def area(polygon): return abs(numpy.cross(polygon, numpy.roll(polygon, -1, 0)).sum() / 2) - iouvxz

Answer 1

这是我所知道的标准方法，在这里可以找到详细信息。基本上是对每个顶点周围的叉积求和。比三角剖分要简单得多。

以下是Python代码，给定表示为(x,y)顶点坐标列表的多边形，并隐式地从最后一个顶点绕回第一个：

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                         for ((x0, y0), (x1, y1)) in segments(p)))

def segments(p):
    return zip(p, p[1:] + [p[0]])

David Lehavi评论道：值得一提的是为什么这个算法有效：它是应用了函数−y和x的Green定理，就像平面积分器的工作方式一样。更具体地说：

上述公式 =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area

- Darius Bacon

---

值得一提的是，这个算法为什么有效： 它是应用了对函数-y和x的Green定理，就像平面计算仪一样工作。更具体地说： 上述公式 = 积分周长(-y dx + x dy) = 积分面积((-(-dy)/dy+dx/dx)dydyx = 2 Area - David Lehavi

帖子中的链接已失效，有没有其他的链接？ - YAKOVM

@perfectionm1ng 转换方向会翻转总和中的符号，但是 abs() 函数会去除符号。 - Darius Bacon

限制：这种方法将为自相交的多边形生成错误的答案，其中一条边横跨另一条边，如右图所示。但对于三角形、正多边形和不规则多边形、凸多边形或凹多边形，它仍然可以正确地工作。（来源：http://www.mathopenref.com/coordpolygonarea.html） - OneWorld

这也被维基百科称为“鞋带公式”（Shoelace formula）。 - PHPirate

Answer 2

向量叉积是一个经典问题。

如果你需要进行大量这样的计算，请尝试以下经过优化的版本，它只需要一半的乘法操作：

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不是偶数，则追加另一个第一点的副本。

该算法通过展开和合并经典叉积算法的连续两个迭代获得。

我不确定这两种算法在数值精度方面如何比较。我的印象是上述算法比经典算法更好，因为乘法 tends tend to restore the loss of precision of the subtraction。当受到浮点数限制时（例如GPU），这可能会产生显着差异。

编辑：“二维和三维三角形和多边形的面积”描述了一种更有效的方法。

// "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;

- chmike

---

这是对上述算法的正确数学重排，节省了一些乘法。你是对的，但是其他顶点定义的区域将被减去。但这可能会导致精度降低。 - chmike

你忽略了一个事实，由于y的减法，加法始终会有一些负项。考虑任何2D多边形图形，并比较相邻顶点的y值。你会发现有些减法会产生负值，而有些则是正的。 - chmike

确实，我无法理解最后一段话！使用 i <= N 就可以了。感谢您的耐心，我收回之前的话 :) - Cygon

顺便提一下，算法返回的区域是“有符号的”（根据点的顺序为负或正），因此如果您想始终使用正面积，请使用绝对值。 - NightElfik

第一个算法很危险。如果只有4个点，第一次迭代后可能会访问数组后面的位置。 - ploth

Answer 3

这个网页展示了一个公式：

可以简化为：

如果你将一些项写出来并按照xi的公共因子进行分组，则等式不难看出。

最终的求和计算更高效，因为它只需要进行n次乘法而非2n次。

def area(x, y):
    return abs(sum(x[i] * (y[i + 1] - y[i - 1]) for i in xrange(-1, len(x) - 1))) / 2.0

我从Joe Kington（这里）学到了这个简化方法。

---

如果您有NumPy，那么这个版本会更快（对于除了非常小的数组之外的所有情况）：

def area_np(x, y):        
    x = np.asanyarray(x)
    y = np.asanyarray(y)
    n = len(x)
    shift_up = np.arange(-n+1, 1)
    shift_down = np.arange(-1, n-1)    
    return (x * (y.take(shift_up) - y.take(shift_down))).sum() / 2.0

- unutbu

---

此答案为@chmike的回答中第二个算法提供了数学解释。看起来它是本页面所有答案中最有效的。 - Константин Ван

Answer 4

为了进一步解释三角测量和三角形面积之和，如果您恰好有一个凸多边形或选择一个不会生成与多边形相交的每个其他点的线的点，则可以使用它们。

对于一般的非相交多边形，您需要对向量（参考点，点a），（参考点，点b）的叉积求和，其中a和b“相邻”。

假设您有一个按顺序定义多边形的点列表（顺序是点i和i + 1形成多边形的线）：

从i = 1到n-1求和((point0，pointi)，(point0，pointi + 1))的叉积。

取该叉积的大小，即可得到表面积。

这将处理凹多边形，而无需担心选择好的参考点；任何生成不在多边形内的三角形的三个点都具有指向与多边形内部三角形相反方向的叉积，因此面积被正确地求和。

- MSN

Answer 5

一组没有其他约束的点不一定能唯一地定义一个多边形。

因此，您首先需要决定从这些点中构建什么样的多边形——也许是凸包？http://en.wikipedia.org/wiki/Convex_hull

然后三角剖分并计算面积。http://www.mathopenref.com/polygonirregulararea.html

- mbeckish

---

原帖中提到“一系列点”，这是一个有序的点集。有序的点集定义了一个多边形。 - Константин Ван

Answer 6

计算多边形的面积

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1#polygon_area

int cross(vct a,vct b,vct c)
{
    vct ab,bc;
    ab=b-a;
    bc=c-b;
    return ab.x*bc.y-ab.y*bc.x;
}    
double area(vct p[],int n)
{ 
    int ar=0;
    for(i=1;i+1<n;i++)
    {
        vct a=p[i]-p[0];
        vct b=p[i+1]-p[0];
        area+=cross(a,b);
    }
    return abs(area/2.0);
}    

- Steve

---

这是一个已有3年历史的问题，其被采纳的答案得到了34个赞。请告诉我们你的回答比已经发布的其他任何答案都更好。 - Mark Taylor

这是C语言的示例，而不是Python。并非更好，但用不同的语言表达很不错。 - underdoeg

你的 cross() 函数需要 3 个参数，但你只给了 2 个吗？ - oarfish

Answer 7

可以使用Numpy实现鞋带公式。假设这些顶点：

import numpy as np
x = np.arange(0,1,0.001)
y = np.sqrt(1-x**2)

我们可以定义以下函数来计算面积：

def PolyArea(x,y):
    return 0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1)))

获取结果：

print PolyArea(x,y)
# 0.26353377782163534

避免循环使此函数比 PolygonArea 快约50倍：

%timeit PolyArea(x,y)
# 10000 loops, best of 3: 42 µs per loop
%timeit PolygonArea(zip(x,y))
# 100 loops, best of 3: 2.09 ms per loop

注意：我为另一个问题编写了这个答案，我在这里提到这一点是为了有一个完整的解决方案列表。

- Mahdi

Answer 8

一种方法是将多边形分解成三角形，计算三角形的面积，并将它们相加得到多边形的面积。

- MattK

Answer 9

1. 设定一个基准点（最凸出的点）。这将是你三角形的枢轴点。
2. 计算除了基准点之外的最左边的点（任意选择）。
3. 计算第二个最左边的点以完成你的三角形。
4. 保存这个三角形区域。
5. 每次迭代向右移动一个点。
6. 求和三角形面积。

- d03boy

---

请确保如果下一个点向“后”移动，则取反三角形面积。 - recursive

Answer 10

或者进行等高线积分。斯托克斯定理允许您将面积积分表示为等高线积分。再加上一点高斯求积，就大功告成了。

- duffymo