91

假设二维空间中的一系列点不自相交，那么确定所得多边形面积的有效方法是什么？

作为旁注，这不是家庭作业，我不是在寻找代码。我正在寻找可以用来实现我自己的方法的描述。我有关于从点列表中拉出一系列三角形的想法，但我知道有很多关于凸多边形和凹多边形的边缘情况，我可能无法捕捉到。

4

16 回答 16

119

这是标准方法，AFAIK。基本上总结每个顶点周围的叉积。比三角测量简单得多。

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 的应用；完全按照平面计的工作方式。进一步来说：

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

于 2009-01-16T18:39:05.157 回答
14

叉积是经典。

如果你有无数次这样的计算要做，试试下面的优化版本，它需要少一半的乘法：

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;
于 2009-04-04T16:38:57.343 回答
13

此页面显示公式

在此处输入图像描述

可以简化为：

在此处输入图像描述

如果写出几个项，按照 的公因数分组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
于 2013-11-09T11:48:55.767 回答
5

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

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

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

于 2009-01-16T18:34:18.723 回答
5

为了扩展三角形和求和三角形区域，如果您碰巧有一个凸多边形，或者您碰巧选择了一个不会生成与多边形相交的每个其他点的线的点，这些都可以工作。

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

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

Sum(叉积 ((point 0, point i), (point 0, point i + 1)) for i = 1 to n - 1。

取那个叉积的大小，你就有了表面积。

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

于 2009-01-16T18:40:31.830 回答
3

计算多边形的面积

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);
}
于 2012-10-04T15:05:38.503 回答
2

或者做一个轮廓积分。斯托克斯定理允许您将面积积分表示为等高线积分。一点高斯求积和鲍勃是你的叔叔。

于 2009-01-16T18:33:40.393 回答
2

语言无关的解决方案：

给定：多边形总是由不重叠的 n-2 个三角形组成（n = 点数或边数）。1 个三角形 = 3 边多边形 = 1 个三角形；1 个正方形 = 4 个多边形 = 2 个三角形；等等恶心QED

因此，可以通过“切掉”三角形来减少多边形，总面积将是这些三角形面积的总和。用一张纸和剪刀试一试，最好在跟随之前想象一下这个过程。

如果您在多边形路径中选取任意 3 个连续点并使用这些点创建一个三角形，您将遇到以下三种可能场景中的一种且只有一种：

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

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

每次找到其中一个时，我们将其切掉，计算其面积（简单易懂，此处不解释公式）并制作一个边少的新多边形（相当于切掉这个三角形的多边形）。直到我们只剩下一个三角形。

如何以编程方式实现：

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

此外，如果您希望与地图集成并从地理点开始，则必须首先从地理点转换为屏幕点。这需要确定地球形状的模型和公式（尽管我们倾向于将地球视为一个球体，但它实际上是一个不规则的卵形（蛋形），带有凹痕）。那里有很多模型，有关更多信息 wiki。一个重要的问题是您是否会将该区域视为平面还是弯曲的。通常，如果考虑平面而不是凸面，则点相距几公里的“小”区域不会产生明显的误差。

于 2011-08-21T15:06:08.337 回答
1

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

于 2009-01-16T18:24:40.113 回答
1
  1. 设置一个基点（最凸的点）。这将是三角形的轴心点。
  2. 计算最左边的点（任意），而不是你的基点。
  3. 计算第二个最左边的点来完成你的三角形。
  4. 保存这个三角形区域。
  5. 每次迭代向右移动一个点。
  6. 对三角区域求和
于 2009-01-16T18:25:57.320 回答
1

比对三角形求和更好的是在笛卡尔空间中对梯形求和：

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;
}
于 2009-01-16T19:34:35.870 回答
1

鞋带公式的实现可以在 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

避免循环使该函数比以下函数快约 50 倍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

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

于 2015-06-20T06:07:23.517 回答
0

我的倾向是简单地开始切掉三角形。我看不出还有什么办法可以避免毛茸茸的。

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

于 2009-01-16T18:23:55.047 回答
0

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;
}
于 2015-12-02T21:27:54.327 回答
0

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

//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;
}
于 2017-04-02T22:47:44.860 回答
0

Python代码

如此处所述：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
于 2017-09-29T06:29:58.223 回答