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

假设2d空间中的一系列点不是自相交的,那么确定结果多边形面积的有效方法是什么？

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

1> Darius Bacon..：

---

这是标准方法,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 的Green定理的应用; 正是在一个测量计的工作方式.进一步来说:

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

---

值得一提的是这个算法的工作原理:它是函数-y和x的格林定理的应用; 正是在一个测量计的工作方式.更具体地说:上面的公式= integral_permieter(-y dx + x dy)= integral_area(( - ( - dy)/ dy + dx/dx)dydyx = 2 Area

---

帖子中的链接已经死了.有人有另一个吗？

---

限制:此方法将为自相交多边形产生错误答案,其中一侧与另一侧交叉,如右图所示.然而,对于三角形,规则和不规则多边形,凸多边形或凹多边形,它将正常工作.(http://www.mathopenref.com/coordpolygonarea.html)

---

@perfectionm1ng切换方向将翻转总和中的符号,但`abs()`剥离符号.

2> chmike..：

---

交叉产品是经典之作.

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

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;

---

你忽略的是,由于y减法,加法总是有一些否定词.考虑任何2d多边形形状并比较连续顶点的y值.你会看到一些减法会产生负值而一些是正值.

---

的确,最后一段是我无法理解的!当i <= N时,它可以工作.谢谢你的耐心,我把一切都拿回来:)

3> unutbu..：

---

此页面显示该公式

可以简化为:

如果你写出一些术语并根据共同因素对它们进行分组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

我学会了从乔金顿这样的简化,在这里.

---

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