这里是 the standard method 。基本上求和每个顶点的交叉积。比三角测量简单得多。

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]])

DavidLehavi评论:值得一提的是,这个算法为什么有效:它是 Green's theorem 对于函数“y”和“x”;完全按照a planimeter 作品。更具体地说:

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

交叉积是一个经典。

如果您有无数这样的计算要做,请尝试以下需要少一半乘法的优化版本:

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不是偶数,则附加第一个点的额外副本。

该算法是通过展开并结合经典交叉积算法的两个连续迭代得到的。

我不太确定这两种算法在数值精度方面的比较。我的印象是,上面的算法比经典算法好,因为乘法往往会恢复减法的精度损失。当限制使用float时,就像使用gpu一样,这可能会产生显著的差异。

编辑: "Area of Triangles and Polygons 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;

This page 显示公式

可以简化为:

如果你写出一些术语,并根据 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

我从乔·金顿那里学到了这种简化, here .

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

没有任何其他约束的点集不一定唯一地定义多边形。

所以,首先你必须决定从这些点构建什么多边形——也许是凸面外壳? http://en.wikipedia.org/wiki/Convex_hull

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

为了在三角形区域上展开并求和,如果您碰巧有一个凸多边形,或者您碰巧选择了一个点,该点不会生成到与多边形相交的每个其他点的线。

对于一般的非相交多边形,需要求和向量(参考点,A点),(参考点,B点)的交叉积,其中A和B是“相邻”的。

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

i=1到n-1的和(叉积((点0,点I),(点0,点I+1))。

取这个叉积的大小,你就得到了表面积。

这将处理凹面多边形,而不必担心选择一个好的参考点;任何三个点生成一个不在多边形内的三角形都将有一个交叉积,该交叉积指向多边形内任何三角形的相反方向,因此面积得到正确的求和。

计算多边形面积的步骤

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

或者做一个轮廓积分。斯托克斯定理允许将面积积分表示为轮廓积分。有点高斯正交和鲍勃的叔叔。

一种方法是 decompose the polygon into triangles ,计算三角形的面积,并取和作为多边形的面积。

1. 设置基点(最凸点)。这将是三角形的轴心点。
2. 计算最左侧的点(任意),而不是基点。
3. 计算第二个最左边的点来完成三角形。
4. 保存此三角形区域。
5. 每次迭代向右移动一个点。
6. 对三角形区域求和

与三角形求和相比,笛卡尔空间中的梯形求和更好:

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

语言独立解决方案:

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

因此,可以通过“切掉”三角形来减少多边形,总面积将是这些三角形的面积之和。试着用一张纸和一把剪刀,如果你能在接下来的过程中看到它是最好的。

如果在多边形路径中取任意3个连续点,并使用这些点创建三角形,则可能会有三种情况之一:

1. 生成的三角形完全在原始多边形内
2. 生成的三角形完全在原始多边形之外
3. 生成的三角形部分包含在原始多边形中

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

每次我们找到其中的一个,我们就把它切掉,计算它的面积(简单易懂,这里不解释公式),然后做一个新的边少的多边形(相当于这个三角形切掉的多边形)。直到我们只剩下一个三角形。

如何通过编程实现:

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

此外,如果您希望与地图集成并从地理点开始,则必须先从地理点转换为屏幕点。这需要确定一个地球形状的模型和公式(尽管我们倾向于把地球看作一个球体,但实际上它是一个不规则的卵圆形(蛋形),带有凹痕)。有许多模型,为进一步的信息维基。一个重要的问题是你是否会认为这个区域是一个平面或者是曲线。一般来说,如果考虑到平面和非凸面,点间距达千米的“小”区域不会产生显著误差。

执行 Shoelace formula 可以在麻木中完成。假设这些顶点:

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 :

%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

注意:我已经为另一个人写了这个答案 question ,我只是在这里提到了一个完整的解决方案列表。

我倾向于简单地开始切掉三角形。我不明白还有什么能避免长得毛茸茸的。

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

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

蟒蛇代码

如下所述: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

与熊猫

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

我将给出一些计算二维多边形面积的简单函数。这对凸多边形和凹多边形都适用。 我们简单地把多边形分成许多小三角形。

//don't forget to include cmath for abs function
struct Point{
  double x;
  double y;
}
// cross_product
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;
}