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

Question

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

附带说明一下，这不是家庭作业，我也不是在寻找代码。我正在寻找可用于实现我自己的方法的描述。我有关于从点列表中提取一系列三角形的想法，但我知道有很多关于凸多边形和凹多边形的边缘情况我可能不会捕捉到。

Answer 1

这里是 the standard method ， 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 评论:值得一提的是这个算法为什么有效:它是 Green's theorem 的一个应用。对于函数 −y 和 x；完全按照planimeter的方式作品。更具体地说:

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