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

对于(凸)四边形,将四边形拆分为两个三角形并计算两个三角形的面积通常更快。

如果四边形不保证凸形,则 closed polygon approach 仍然是我的首选,因为它通常比检查更快,以确定如何正确地分割四元。

根据注释编辑:

正如Walt W所指出的,这两种方法在理论上在性能上是相同的。第二个更灵活,因为不需要凸四边形,但是第一个(拆分三角形)更容易实现和理解,因此可能更易于维护。

不。我会用你提到的帖子里的公式。

编辑:

为了详细说明这一点,你在文中提到的方法(在里德·科普西的回答中称为闭合多边形方法)最终将点列表分解成三角形,并使用交叉积计算它们的面积。根据描述多边形的点的顺序(缠绕),它不需要利用正区域和负区域来三角化任何东西。因为它同时利用了正区域和负区域,所以这种方法不需要对构成四边形中每个三角形的线进行任何计算,而且四边形是否是凸的也不重要。

也就是说,在概念上更容易理解将四边形分解为两个不重叠的三角形,并独立计算每个三角形的面积。这种方法也将始终产生正确的结果。这种方法的复杂之处在于决定哪对相对的顶点应该指定两个三角形之间的断点。如果你有一个非凸四边形并且选择了错误的三角测量,那么你最终会得到重叠的三角形(除非考虑到),这将扭曲区域结果。如果在计算这些三角形的面积时要注意,你会发现(特别是四边形的情况下)一个三角形总是包含在另一个三角形中。有了一些聪明,你可以得到包含三角形的区域与包含三角形的区域有相反的符号,这将再次产生正确的结果。

本质上,这两种算法是相同的。没有性能差异;假设四元由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个操作。完全相同的操作数。

因此,最大的区别在于,三角剖分之后是交叉积面积计算更容易理解,因为它非常简单,而闭合多边形方法实际上只是相同的算法,但经过了优化,从而以不同的方式呈现。

总之,是的,你提到的帖子中的公式是你所得到的最有效的公式,同时也是最简单的算法,当提出不同的时候。

这个 mathworld 页面列出了几个公式。

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

一旦你有了两个三角形, Heron's Formula 在计算机程序中工作良好。

对于A、B和C边的三角形,面积为

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

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