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

Question

假设多边形不会自相交，那么怎样才能以最高效的方式完成这个任务呢？该多边形有 N 个顶点。 虽然可以通过坐标计算，但是否还有其他通用方法呢？

- rgs

---

除了使用坐标之外，还有其他方法吗？ - Beta

让我向您介绍http://math.stackexchange.com，这里有人很好地回答数学问题。 - Déjà vu

@ringø 这是一个非常好的编程问题。没有针对你个人的意思，但那些认为任何涉及一点数学的问题不算编程问题的 Stack Overflow 社区成员真的在对社区做出了不好的贡献。 - Gene

@Gene 根本不是这样。一些数学问题（复杂度、博弈论等）通常可以在SO上找到实用的答案（没有太多理论和积分参与）。然而，对于这个特定的问题，它应该是数学家易如反掌的事情，算术公式也很容易被编程，并且可以立即由其他数学家进行检查和确认，所以在我看来，math.SE是一个好选择。没有任何针对您个人的意思，这就是我会做的事情。纯粹的慷慨建议...没有其他意图... - Déjà vu

你目前尝试了什么？此外，添加一些漂亮的图片将有助于其他人更好地理解你的问题。 - Wai Ha Lee

Answer 1

有向面积，A(T)，是指三角形 T = ((x1, y1), (x2, y2), (x3, y3)) 的面积，其定义为下列矩阵行列式的一半：

|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)

这是一个线性时间算法，并且很容易并行化。还要注意，当您的顶点坐标都是整数时，它是一个精确的算法。

链接到维基百科上关于这个算法的文章

- Timothy Shields

---

这是最好的答案，但您应该扩展A()函数。另请注意，在这些A()调用中，使用什么作为p [0]并不重要，因此您可以使用（0,0）常量并节省一些操作。 - Matt Timmermans

非常有趣。如果你只需要知道多边形的总面积（就像这种情况下的 OP 一样），我想进行实际三角剖分毕竟是过度的（尽管一旦完成了计算出每个三角形的面积，计算总面积确实很简单）。 - Nicolas Miari

这是一个Matlab的一行版本：area = abs(sum(sum(vertices .* (circshift(vertices, [1 0]) * [0 1;-1 0]))))/2; - Jed

Answer 2

我能想到的最好方法是将多边形视为几个三角形，分别计算它们的面积并将它们相加以得出总面积。所有的多边形，无论规则还是不规则，本质上都只是一堆三角形（将四边形对角线切成两个三角形，五边形在一个角落斜着切两下，依此类推）。这个过程很容易用代码实现。

以下是通用算法：

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坐标。

该算法从先前的顶点迭代地构建三角形。

我从Math Open Ref提供的算法进行了修改。

将其适应于您存储坐标的形式以及您在项目中使用的任何语言应该是相对容易的。

- rp.beltran

---

我认为你的答案没有任何问题。那些是带符号的梯形面积，而不是三角形，如果它们重叠也完全没问题。实际上，如果顶点被存储为具有定义交叉积运算符的2D向量，则可以简化为sum(v[i] ^ v[i+1])。 - Anton Knyazyev

@AntonKnyazyev 好的，谢谢，我已经移除了警告。 - rp.beltran

正确的想法，但是数学计算有误。Timothy Shields的回答最佳。 - Jed

@Jed 如果你发现了错误，我很乐意接受更正（我是在高中时完成的，如果有些地方有点粗糙，我也不会感到惊讶），但经过简要查看和尝试几个例子后，我认为这里的数学是正确的。有什么例外情况吗？请注意，Xcoords和Ycoords的顺序显示它们连接的顺序，这一点我似乎从未澄清过。 - rp.beltran

@rp.beltran。非常抱歉...你是完全正确的！Timothy Shields的答案与您的答案等效，尽管它们的表述方式有所不同。我仍然（非常轻微地）更喜欢他的答案，因为每次增加面积都是连接原点和两个线段的三角形（在/2之后）的（有符号）面积，这对我来说更直观。不过，一旦将所有内容添加起来，您的答案仍然相同。感谢您帮助我发现我的错误 :-) - Jed

@Jed没问题，很高兴有更多的人来检查事情！我认为我更喜欢他的答案，特别是因为我觉得我的解释不足。我只是想确保没有技术上的不准确之处。 - rp.beltran

Answer 3

1. 从多边形中取出连续的3个点。
2. 计算形成的三角形的面积。
3. 从多边形中删除中间的那个点。
4. 对已剩下的多边形进行测试，判断被删除的点是否在其内部。如果在内部，则将三角形面积从总面积中减去，否则加上。
5. 重复以上步骤，直到多边形只剩下一个三角形，并将该三角形的面积加入总面积。

编辑：为了解决@NicolasMiari提出的问题，可以进行两次操作，第一次仅处理位于剩余多边形内部的顶点，第二次处理剩余的顶点。

- Mark Ransom

---

这个程序的运行时间会是多少？ - rgs

从问题来看，“最有效的方法是什么？” 直接实现至少为O(N^2)。为什么会有那么多人赞同一个给出高度次优算法的答案，而这个问题已经有一个已知的简单O(N)解决方案呢？计算非凸多边形的面积与计算凸多边形的面积没有任何区别，实际上两种情况下的最优算法是相同的。然而，问题和排名第一的答案会让任何只是浏览的人认为你需要一个复杂的算法来处理非凸情况。这是非常误导人的。 - Timothy Shields

@TimothyShields 我的算法很直观，而你的不是，但你提供的维基百科链接帮了很大忙。别担心，好的东西总会脱颖而出。 - Mark Ransom

@SGR 第四步可能会有点慢，但如果你知道顶点是按顺时针还是逆时针排序的话，就可以加速了。除此之外，它应该是O(n)的。 - Mark Ransom

进行一次操作后不能保证得到一个凸多边形，因此即使进行两次操作，你仍可能遇到类似Miari所展示的情况。实际上，在一般情况下没有有限次操作可以保证得到一个凸多边形，因此这个算法似乎有些棘手。Shields算法非常直观和简单。 - Jed

Answer 4

“一次只撕下一个三角形”的算法是有效的，前提是您撕下的三角形不包含“洞”（多边形的其他顶点）。

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

然而，这是有可能的（现在无法数学证明，但你必须相信我）。您只需要遍历多边形的顶点并执行一些包含测试，直到找到合适的三角形。

来源：我曾根据 Joseph O'Rourke 的 C语言计算几何中所述实现了任意非交多边形的三角剖分。

- Nicolas Miari