如何计算非凸多边形的面积？ [英] How do I calculate the area of a non-convex polygon?

问题描述

假设多边形不自相交，那么最有效的方法是什么？多边形有N个顶点。
我知道可以用坐标来计算，但是还有另一种通用方法吗？

Assuming that the polygon does not self-intersect, what would be the most efficient way to do this? The polygon has N vertices. I know that it can be calculated with the coordinates but is there another general way?

推荐答案

三角形 T =（（（x1，y1），（x2，y2），（）的符号区域， A（T） x3，y3））定义为以下矩阵的行列式的1/2倍：

The signed area, A(T), of the triangle T = ((x1, y1), (x2, y2), (x3, y3)) is defined to be 1/2 times the determinant of the following matrix:

|x1 y1 1|
|x2 y2 1|
|x3 y3 1|

行列式为 -y1 * x2 + x1 * y2 + y1 * x3 -y2 * x3-x1 * y3 + x2 * y3 。

给出顶点<$ c定义的多边形（凸形或凹形） $ c> p [0]，p [1]，...，p [N-1] ，您可以按如下方式计算多边形的面积。

Given a polygon (convex or concave) defined by the vertices p[0], p[1], ..., p[N - 1], you can compute the area of the polygon as follows.

area = 0
for i in [0, N - 2]:
    area += A((0, 0), p[i], p[i + 1])
area += A((0, 0), p[N - 1], p[0])
area = abs(area)

使用上述行列式的表达式，您可以计算 A（（0，0 ），p，q）作为 0.5 *（-py * qx + px * qy）有效。进一步的改进是只乘一次 0.5 ：

Using the expression for the determinant above, you can compute A((0, 0), p, q) efficiently as 0.5 * (-p.y*q.x + p.x*q.y). A further improvement is to do the multiplication by 0.5 only once:

area = 0
for i in [0, N - 2]:
    area += -p[i].y * p[i+1].x + p[i].x * p[i+1].y
area += -p[N-1].y * p[0].x + p[N-1].x * p[0].y
area = 0.5 * abs(area)

这是线性时间算法，并行化很简单。还要注意，当顶点的坐标都是整数值时，这是一种精确的算法。

This is a linear time algorithm, and it is trivial to parallelize. Note also that it is an exact algorithm when the coordinates of your vertices are all integer-valued.

链接到有关此算法的Wikipedia文章

这篇关于如何计算非凸多边形的面积？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！