如何计算非凸多边形的面积？

Question

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

Answer 1

解决这个问题的最好办法就是将多边形看作几个三角形，分别找到它们的区域，然后将它们总计为总面积。所有多边形，规则的或不规则的，基本上只是一堆三角形（对角线切成四边形以形成两个三角形，五角形从一个角落到两个最相反的三角形，并且模式继续）。这对代码很简单。

一种用于这种通用算法可以被编码如下：

function polygonArea(Xcoords, Ycoords) { 
    numPoints = len(Xcoords) 
    area = 0;   // Accumulates area in the loop 
    j = numPoints-1; // The last vertex is the 'previous' one to the first 

    for (i=0; i<numPoints; i++) 
    { area = area + (Xcoords[j]+Xcoords[i]) * (Ycoords[j]-Ycoords[i]); 
     j = i; //j is previous vertex to i 
    } 
    return area/2; 
} 

Xcoords和Ycoords是数组，其中Xcoords存储X坐标，并Ycoords的Y坐标。

该算法从以前的顶点迭代构造三角形。

我修改这个从提供Here by Math Open Ref

它应该是相对无痛这个适应任何形式的你是存储在您的坐标算法，和任何语言使用的是为您的项目。

Answer 2

1. 从多边形中取3个连续的点。
2. 计算所得三角形的面积。
3. 从多边形中移除3个点的中点。
4. 做一个测试，看看移除的点是否在剩余的多边形内。如果它在里面从总数中减去三角形区域，否则添加它。
5. 重复，直到多边形由一个三角形组成，并将该三角形的面积添加到总数。

编辑：解决由@NicolasMiari给出简单地使两道次，在第一道次的问题仅处理是内部其余多边形，在第二次处理，其余的顶点。

Answer 3

只要您移除的三角形不包含“孔”（多边形的其他顶点），“一次撕开一只耳朵”算法就可以工作。

也就是说，你需要选择下面的绿色三角形，不红色的：

然而，它始终是可以这样做（不能证明数学现在，但你必须相信我）。您只需走多边形的顶点并执行一些包含测试，直到找到合适的三元组。

来源：我曾经根据我在Computational Geometry in C by Joseph O'Rourke中读到的内容实现了任意非相交多边形的三角剖分。

Answer 4

的签面积，A(T)，三角形T = ((x1, y1), (x2, y2), (x3, y3))的被定义为以下矩阵的1/2倍的行列式：

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

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

给定一个多边形由顶点定义p[0], p[1], ..., p[N - 1]（凸或凹），则可以如下计算多边形的面积。

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 * (-p.y*q.x + p.x*q.y)。进一步的改进是0.5做乘法只有一次：

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) 

这是一个线性时间算法，这是微不足道的并行。还要注意，当顶点的坐标都是整数值时，它是一个精确的算法。

Link to Wikipedia article on this algorithm