计算四边形面积的好算法是什么？

Question

我看到有一个关于一般多边形的好问题在这里。是否有针对四边形更简单或更有效的算法？

- C. Dragon 76

Answer 1

对于一个凸四边形，通常更快的方法是将四边形分成两个三角形，并计算这两个三角形的面积。

如果四边形不能保证是凸的，则闭合多边形方法仍然是我的首选，因为它通常比检查如何正确地分割四边形更快。

---

根据Walt W的指出，这两种方法在性能上理论上相同。第二种方法（闭合多边形）由于不需要凸四边形更加灵活，但第一种方法（分割三角形）更容易实现和理解，因此可能更易于维护。

- Reed Copsey

---

你会用哪个公式来计算每个三角形的面积？ - Walt W

你可以采用任何方法。我通常使用两个向量的叉积的一半，但这是因为我几乎总是在三维空间中工作，并且对于非平面四边形有效（尽管在这种情况下，技术上应该使用规则曲面，但这不是快速的方法）。 - Reed Copsey

仅供参考，我真的只是客观地试图弄清楚这个问题……但是当我进行叉积计算时，我得到一个三角形：(x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0) = area * 2 = 7 次操作。对于两个三角形，再乘以0.5，总共需要15次操作。然而，一般方法（如下面我的回答）只需要13次操作。我错了吗？我可能真的错了。但是我错了吗？ - Walt W

我相信，如果正确实现，这两种方法在操作上几乎完全等效。斯托克斯定理（第二种方法所基于的）我相信是从三角剖分开始，并推导出第二种方法。我认为其中一种并不比另一种“更好”-除非有理由选择其他方式，否则我会选择易于理解的第一种方法。 - Reed Copsey

好的，我会争论实现的容易程度，但这样也可以；）谢谢。 - Walt W

Answer 2

不是的。我会使用您提到的帖子中的公式。

编辑：

更详细地说，您提到的帖子中介绍的方法（在Reed Copsey的答案中称为封闭多边形方法）确实将点列表分成三角形，并使用叉积计算它们的面积。通过利用描述多边形的点的排序（缠绕），它利用了正面和负面区域，因此可以避免任何计算四边形中构成每个三角形的线条，并且无论四边形是否凸都没有关系。

话虽如此，将四边形分成两个不重叠的三角形并独立计算每个三角形的面积在概念上更容易理解。这种方法也总是能得出正确的结果。这种方法的复杂之处在于决定哪对相对顶点应该指定两个三角形之间的断裂。如果您有一个非凸四边形并选择错误的三角剖分，则最终会得到重叠的三角形（除非考虑到），这将使面积结果偏斜。如果在计算这些三角形的面积时采取一些小心措施，您会发现（在特定情况下是四边形的情况下）一个三角形始终包含在另一个三角形中。通过一些聪明的方法，您可以使包含的三角形的面积与包含的三角形的面积相反，这将再次产生正确的结果。

实质上，这两个算法是相同的。没有性能差异；假设quad由x0、y0、x1、y1、x2、y2、x3和y3指定。然后封闭多边形方法具有以下操作：

area = 0.5 * abs( x0 * y1 - x1 * y0 + x1 * y2 - x2 * y1 + 
  x2 * y3 - x3 * y2 + x3 * y0 - x0 * y3 )

这可以简化为：

area = 0.5 * abs( x0 * (y1 - y3) + x1 * (y2 - y0) + x2 * (y3 + y1) + 
  x3 * (y0 - y2) )

这相当于（数一下*和+的个数）总共需要12个操作。另一种方法是找到每个单独的三角形并进行叉乘，具体步骤如下：

x2_line = x2 - x0
y2_line = y2 - y0
area = 0.5 * abs( (x1 - x0) * y2_line + (y1 - y0) * x2_line + 
  x2_line * (y3 - y0) + y2_line * (x3 - x0) )

这句话可以简化为：

x2_line = x2 - x0
y2_line = y2 - y0
area = 0.5 * abs( y2_line * (x1 - x0 + x3 - x0) + x2_line * (y1 - y0 + y3 - y0) )

这也意味着有12个操作。确切地说是相同数量的操作。

因此，最大的区别在于三角测量和叉积面积计算更容易理解，因为它非常直观，而封闭多边形方法实际上只是相同的算法，但经过优化并以不同的方式呈现。

总之，是的，你提到的帖子中的公式是你所拥有的最有效的公式，同时也是最简单的算法，当以不同的方式呈现时。

- Walt W

---

为什么要踩这个问题……通用公式每个顶点对需要3次操作加上1次乘以0.5，这相当于一个四边形需要3*4+1=13次操作…… - Walt W

此外，在顶部帖子中提到的封闭多边形方法就是问题中提到的原始公式... - Walt W

起初，它似乎是一个我经常看到的傲慢回答。但是你的编辑和评论让它恢复了。考虑将这些评论放在另一个编辑中。 - geowa4

Answer 3

将四边形分成两个三角形，并计算两个三角形的面积。

一旦你有了两个三角形，海伦公式 在计算机程序中非常有效。

对于一个边长为a、b和c的三角形，其面积为

double area = Math.Sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)/16);

这种方法适用于任何四边形，无论它是矩形、正方形、菱形还是梯形。

- Rap

---

有些四边形不是矩形、正方形、菱形或梯形！如果它们是凸的，像里德指出的那样，“分成两个三角形”是一个非平凡的任务。 - Ken

@Ken：应该是“如果它们不是凸四边形”……凸四边形很简单，因为任何一种断裂都是有效的。非凸四边形可能会导致面积严重过度计算。 - Reed Copsey

那么，最简单的解决方案是计算两组三角形的面积，并选择最小值吗？ - Kirk Broadhurst

Answer 4

MathWorld页面列出了几个公式。

- moonshadow