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

Assuming a series of points in 2d space that do not self-intersect, what is an efficient method of determining the area of the resulting polygon?

假设在二维空间中有一系列不自交的点，那么确定结果多边形面积的有效方法是什么?

As a side note, this is not homework and I am not looking for code. I am looking for a description I can use to implement my own method. I have my ideas about pulling a sequence of triangles from the list of points, but I know there are a bunch of edge cases regarding convex and concave polygons that I probably won't catch.

顺便说一句，这不是家庭作业，我也不是在找代码。我正在寻找一个描述，我可以用来实现我自己的方法。我有我的想法从点的列表中拉出一串三角形，但是我知道有很多关于凸多边形和凹多边形的边缘情况我可能不会理解。

16 个解决方案

#1

Here is the standard method, AFAIK. Basically sum the cross products around each vertex. Much simpler than triangulation.

这是标准方法AFAIK。基本上就是对每个顶点的外积求和。三角测量应用程序要简单得多。

Python code, given a polygon represented as a list of (x,y) vertex coordinates, implicitly wrapping around from the last vertex to the first:

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 comments: It is worth mentioning why this algorithm works: It is an application of Green's theorem for the functions −y and x; exactly in the way a planimeter works. More specifically:

大卫Lehavi评论:值得一提的是为什么这个算法工作原理:它是一个应用格林定理−y和x的函数;就像平面仪一样。更具体地说:

Formula above =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area

上面的公式= integral_over_(-y dx + x dy) = integral_over_area((-(-dy)/dy+dx/dx) = 2区域。

#2

The cross product is a classic.

叉乘是一个经典。

If you have zillion of such computation to do, try the following optimized version that requires half less multiplications:

如果你有大量这样的计算工作要做，可以试试下面的优化版本，它需要的乘法次数少一半:

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;

I use array subscript for clarity. It is more efficient to use pointers. Though good compilers will do it for you.

为了清晰，我使用数组下标。使用指针更有效。尽管优秀的编译器会为你做这些。

The polygon is assumed to be "closed", which means you copy the first point as point with subscript N. It also assume the polygon has an even number of points. Append an additional copy of the first point if N is not even.

多边形被假定为“闭合的”，这意味着你将第一个点复制为带有下标n的点，它还假设多边形有偶数个点。如果N不是偶数，则附加第一点的附加副本。

The algorithm is obtained by unrolling and combining two successive iterations of the classic cross product algorithm.

该算法是通过对经典交叉乘积算法的连续迭代和连续迭代得到的。

I'm not so sure how the two algorithms compare regarding numerical precision. My impression is that the above algorithm is better than the classic one because the multiplication tend to restore the loss of precision of the subtraction. When constrained to use floats, as with GPU, this can make a significant difference.

我不太确定这两种算法在数值精度上有什么不同。我的印象是，上面的算法比经典的算法要好，因为乘法会恢复减法的精度损失。当限制使用浮点数时，就像使用GPU时一样，这可以产生显著的差异。

EDIT: "Area of Triangles and Polygons 2D & 3D" describes an even more efficient method

编辑:“三角形的面积和多边形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;

#3

This page shows that the formula

这个页面显示了公式

can be simplified to:

可以简化为:

If you write out a few terms and group them according to common factors of xi, the equality is not hard to see.

如果你写出一些项并根据xi的共同因子进行分组，就不难看出等式的存在。

The final summation is more efficient since it requires only n multiplications instead of 2n.

最后的求和更有效，因为它只需要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

I learned this simplification from Joe Kington, here.

我从乔·金顿那里学到了这种简化。

---

If you have NumPy, this version is faster (for all but very small arrays):

如果你有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

#4

A set of points without any other constraints don't necessarily uniquely define a polygon.

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

So, first you have to decide what polygon to build from these points - perhaps the convex hull? http://en.wikipedia.org/wiki/Convex_hull

那么，首先你要决定从这些点上构建什么多边形——也许是凸包?http://en.wikipedia.org/wiki/Convex_hull

Then triangulate and calculate area. http://www.mathopenref.com/polygonirregulararea.html

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

#5

To expand on the triangulate and sum triangle areas, those work if you happen to have a convex polygon OR you happen to pick a point that doesn't generate lines to every other point that intersect the polygon.

为了展开三角形和和三角形的区域，如果你碰巧有一个凸多边形或者你碰巧选了一个不生成线的点到与多边形相交的其他点，这些都是可行的。

For a general non-intersecting polygon, you need to sum the cross product of the vectors (reference point, point a), (reference point, point b) where a and b are "next" to each other.

对于一般的非相交多边形，你需要对向量的外积(参考点，点a)求和，(参考点，点b)，其中a和b是“相邻的”。

Assuming you have a list of points that define the polygon in order (order being points i and i+1 form a line of the polygon):

假设你有一个按顺序定义多边形的点列表(顺序为点i和i+1构成多边形的一条线):

Sum(cross product ((point 0, point i), (point 0, point i + 1)) for i = 1 to n - 1.

i = 1到n - 1的和(点0，点i)(点0，点i + 1)

Take the magnitude of that cross product and you have the surface area.

求这个外积的大小就得到了表面积。

This will handle concave polygons without having to worry about picking a good reference point; any three points that generate a triangle that is not inside the polygon will have a cross product that points in the opposite direction of any triangle that is inside the polygon, so the areas get summed correctly.

这将处理凹多边形而不用担心选择一个好的参考点;任何产生一个不在多边形内的三角形的三个点都会有一个叉乘，它指向多边形内的任何三角形的相反方向，所以这些区域会被正确地求和。

#6

To calc the area of the polygon

计算多边形的面积

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

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);
}    

#7

Or do a contour integral. Stokes' Theorem allows you to express an area integral as a contour integral. A little Gauss quadrature and Bob's your uncle.

或者做一个轮廓积分。Stokes定理允许你将面积积分表示为一个轮廓积分。小高斯求积，鲍勃是你叔叔。

#8

One way to do it would be to decompose the polygon into triangles, compute the area of the triangles, and take the sum as the area of the polygon.

一种方法是将多边形分解成三角形，计算三角形的面积，并将和作为多边形的面积。

#9

1. Set a base point (the most convex point). This will be your pivot point of the triangles.
2. 设置一个基点(最大凸点)。这是三角形的主点。
3. Calculate the most-left point (arbitrary), other than your base point.
4. 计算除基点以外的最左点(任意)。
5. Calculate the 2nd-most-left point to complete your triangle.
6. 计算最左2的点来完成你的三角形。
7. Save this triangulated area.
8. 保存这个三角区域。
9. Shift over one point to the right each iteration.
10. 在每次迭代中向右移动一个点。
11. Sum the triangulated areas
12. 和三角地区

#10

Better than summing triangles is summing trapezoids in the Cartesian space:

比加和三角形更好的是加和笛卡尔空间中的梯形:

area = 0;
for (i = 0; i < n; i++) {
  i1 = (i + 1) % n;
  area += (vertex[i].y + vertex[i1].y) * (vertex[i1].x - vertex[i].x) / 2.0;
}

#11

language independent solution:

独立于语言的解决方案:

GIVEN: a polygon can ALWAYS be composed by n-2 triangles that do not overlap (n = number of points OR sides). 1 triangle = 3 sided polygon = 1 triangle; 1 square = 4 sided polygon = 2 triangles; etc ad nauseam QED

给定:多边形总是可以由不重叠的n-2三角形组成(n =点或边的个数)。1个三角形= 3个边多边形= 1个三角形;1个正方形= 4个面多边形= 2个三角形;等令人作呕QED

therefore, a polygon can be reduced by "chopping off" triangles and the total area will be the sum of the areas of these triangles. try it with a piece of paper and scissors, it is best if you ca visualize the process before following.

因此，一个多边形可以通过“切掉”三角形来缩小，其总面积将是这些三角形的面积之和。试着用一张纸和一把剪刀把它剪下来，如果你能在接下来的步骤之前先想象一下这个过程，那就更好了。

if you take any 3 consecutive points in a polygons path and create a triangle with these points, you will have one and only one of three possible scenarios:

如果你在一个多边形路径中取任意3个连续点，并且用这些点创建一个三角形，你将会有一个并且只有三种可能的情形之一:

1. resulting triangle is completely inside original polygon
2. 结果得到的三角形完全在原来的多边形内
3. resulting triangle is totally outside original polygon
4. 得到的三角形完全超出了原来的多边形
5. resulting triangle is partially contained in original polygon
6. 得到的三角形部分包含在原始多边形中

we are interested only in cases that fall in the first option (totally contained).

我们只对属于第一个选项(完全包含)的情况感兴趣。

every time we find one of these, we chop it off, calculate its area (easy peasy, wont explain formula here) and make a new polygon with one less side (equivalent to polygon with this triangle chopped off). until we have only one triangle left.

每次我们找到其中的一个，我们就把它切下来，计算它的面积(很简单，这里不能解释公式)，然后做出一个新的少了一面的多边形(就像切掉这个三角形的多边形)。直到只剩下一个三角形。

how to implement this programatically:

如何以程序方式实施:

create an array of (consecutive) points that represent the path AROUND the polygon. start at point 0. run the array making triangles (one at a time) from points x, x+1 and x+2. transform each triangle from a shape to an area and intersect it with area created from polygon. IF the resulting intersection is identical to the original triangle, then said triangle is totally contained in polygon and can be chopped off. remove x+1 from the array and start again from x=0. otherwise (if triangle is outside [partially or completely] polygon), move to next point x+1 in array.

创建一个(连续的)点数组，这些点表示多边形周围的路径。点0开始。从点x、x+1和x+2运行生成三角形(一次一个)的数组。将每个三角形从一个形状转换为一个区域，并将其与由多边形创建的区域相交。如果得到的交点与原始三角形相同，则该三角形完全包含在多边形中，可以被分割。从数组中删除x+1，然后从x=0开始重新开始。否则(如果三角形在多边形之外[部分或完全])，移动到数组中的下一点x+1。

additionally if you are looking to integrate with mapping and are starting from geopoints, you must convert from geopoints to screenpoints FIRST. this requires deciding a modelling and formula for earths shape (though we tend to think of the earth as a sphere, it is actually an irregular ovoid (eggshape), with dents). there are many models out there, for further info wiki. an important issue is whether or not you will consider the area to be a plane or to be curved. in general, "small" areas, where the points are up to some km apart, will not generate significant error if consider planar and not convex.

此外，如果您希望与映射集成，并且从地理位置开始，您必须首先将地理位置转换为屏幕点。这就需要为地球形状确定一个模型和公式(虽然我们倾向于把地球看作一个球体，但它实际上是一个不规则的卵形(蛋形)，带有凹痕)。有许多模型，为进一步的信息维基。一个重要的问题是你是否会考虑这个区域是一个平面还是一个曲面。一般来说，“小”区域，即点相距几公里，如果考虑平面而非凸，则不会产生明显的误差。

#12

My inclination would be to simply start slicing off triangles. I don't see how anything else could avoid being awfully hairy.

我倾向于开始切割三角形。我看不出还有什么东西能避免这种可怕的毛发。

Take three sequential points that comprise the polygon. Ensure the angle is less than 180. You now have a new triangle which should be no problem to calculate, delete the middle point from the polygon's list of points. Repeat until you have only three points left.

取包含多边形的三个连续点。确保角度小于180度。现在你有了一个新的三角形，应该没问题计算，从多边形的点列表中删除中间点。重复，直到你只剩下三分。

#13

Implementation of Shoelace formula could be done in Numpy. Assuming these vertices:

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

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

We can define the following function to find area:

我们可以定义以下函数来查找区域:

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

And getting results:

得到结果:

print PolyArea(x,y)
# 0.26353377782163534

Avoiding loop makes this function ~50X faster than PolygonArea:

避免循环使该函数比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

Note: I had written this answer for another question, I just mention this here to have a complete list of solutions.

注意:我已经为另一个问题写下了这个答案，我只是在这里提一下，以便有一个完整的解决方案列表。

#14

C way of doing that:

C的方法是:

float areaForPoly(const int numVerts, const Point *verts)
{
    Point v2;
    float area = 0.0f;

    for (int i = 0; i<numVerts; i++){
        v2 = verts[(i + 1) % numVerts];
        area += verts[i].x*v2.y - verts[i].y*v2.x;
    }

    return area / 2.0f;
}

#15

I'm going to give a few simple functions for calculating area of 2d polygon. This works for both convex and concave polygons. we simply divide the polygon into many sub-triangles.

我将给出一些简单的函数来计算二维多边形的面积。这适用于凸多边形和凹多边形。我们只是把多边形分成许多子三角形。

//don't forget to include cmath for abs function
struct Point{
  double x;
  double y;
}

double cp(Point a, Point b){ //returns cross product
  return a.x*b.y-a.y*b.x;
}

double area(Point * vertices, int n){  //n is number of sides
  double sum=0.0;
  for(i=0; i<n; i++){
    sum+=cp(vertices[i]+vertices[(i+1)%n]); //%n is for last triangle
  }
  return abs(sum)/2.0;
}

#16

Python code

As described here: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

这里所描述的那样:http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

With pandas

import pandas as pd

df = pd.DataFrame({'x': [10, 20, 20, 30, 20, 10, 0], 'y': [-10, -10, -10, 0, 10, 30, 20]})
df = df.append(df.loc[0])

first_product = (df['x'].shift(1) * df['y']).fillna(0).sum()
second_product = (df['y'].shift(1) * df['x']).fillna(0).sum()

(first_product - second_product) / 2
600