如何计算二维多边形的面积？
Jas*_*n Z 75 algorithm geometry 2d
假设2d空间中的一系列点不是自相交的,那么确定结果多边形面积的有效方法是什么？
作为旁注,这不是作业,我不是在寻找代码.我正在寻找一个可以用来实现我自己的方法的描述.我有关于从点列表中拉出一系列三角形的想法,但我知道有一些关于凸多边形和凹多边形的边缘情况我可能无法捕捉到.
Dar*_*con 100
这是标准方法,AFAIK.基本上将每个顶点周围的叉积相加.比三角测量简单得多.
Python代码,给定一个表示为(x,y)顶点坐标列表的多边形,隐式地从最后一个顶点环绕到第一个顶点:
def area(p):
return 0.5 * abs(sum(x0*y1 - x1*y0
for ((x0, y0), (x1, y1)) in segments(p)))
def segments(p):
return zip(p, p[1:] + [p[0]])
David Lehavi评论:值得一提的是这个算法的工作原理:它是函数-y和x 的Green定理的应用; 正是在一个测量计的工作方式.进一步来说:
上面的公式=
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area
- 值得一提的是这个算法的工作原理:它是函数-y和x的格林定理的应用; 正是在一个测量计的工作方式.更具体地说:上面的公式= integral_permieter(-y dx + x dy)= integral_area(( - ( - dy)/ dy + dx/dx)dydyx = 2 Area (7认同)
- 帖子中的链接已经死了.有人有另一个吗？ (6认同)
- 限制:此方法将为自相交多边形产生错误答案,其中一侧与另一侧交叉,如右图所示.然而,对于三角形,规则和不规则多边形,凸多边形或凹多边形,它将正常工作.(http://www.mathopenref.com/coordpolygonarea.html) (3认同)
- 这在维基百科上也称为 [鞋带公式](https://en.wikipedia.org/wiki/Shoelace_formula)。 (3认同)
- @perfectionm1ng切换方向将翻转总和中的符号,但`abs()`剥离符号. (2认同)
chm*_*ike 14
交叉产品是经典之作.
如果您要进行大量此类计算,请尝试以下需要减少一半乘法的优化版本:
area = 0;
for( i = 0; i < N; i += 2 )
area += x[i+1]*(y[i+2]-y[i]) + y[i+1]*(x[i]-x[i+2]);
area /= 2;
为清晰起见,我使用数组下标.使用指针更有效.虽然好的编译器会为你做.
假设多边形为"闭合",这意味着您将第一个点复制为带有下标N的点.它还假设多边形具有偶数个点.如果N不均匀,则附加第一个点的附加副本.
该算法是通过展开和组合经典叉积算法的两个连续迭代而获得的.
我不太确定两种算法在数值精度方面的比较.我的印象是上述算法优于经典算法,因为乘法往往会恢复减法精度的损失.当受限制使用浮动时,与GPU一样,这可以产生显着差异.
编辑:"三角形和多边形2D和3D区域"描述了一种更有效的方法
// "close" polygon
x[N] = x[0];
x[N+1] = x[1];
y[N] = y[0];
y[N+1] = y[1];
// compute area
area = 0;
for( size_t i = 1; i <= N; ++i )
area += x[i]*( y[i+1] - y[i-1] );
area /= 2;
- 这是上述算法的正确数学重新排列，节省了一些乘法。你是对的，但是其他顶点定义的面积会减去。但这确实可能会导致精度下降。 (2认同)
- 你忽略的是,由于y减法,加法总是有一些否定词.考虑任何2d多边形形状并比较连续顶点的y值.你会看到一些减法会产生负值而一些是正值. (2认同)
- 的确,最后一段是我无法理解的!当i <= N时,它可以工作.谢谢你的耐心,我把一切都拿回来:) (2认同)
- 顺便说一句，算法返回的面积是“有符号的”（根据点的顺序为负或正），因此如果您希望面积始终为正，则只需使用绝对值。 (2认同)
此页面显示该公式
可以简化为:
如果你写出一些术语并根据共同因素对它们进行分组xi,那么平等就不难看出.
最终求和更有效,因为它只需要n乘法而不是2n.
def area(x, y):
return abs(sum(x[i] * (y[i + 1] - y[i - 1]) for i in xrange(-1, len(x) - 1))) / 2.0
我学会了从乔金顿这样的简化,在这里.
如果你有NumPy,这个版本更快(对于所有但非常小的数组):
def area_np(x, y):
x = np.asanyarray(x)
y = np.asanyarray(y)
n = len(x)
shift_up = np.arange(-n+1, 1)
shift_down = np.arange(-1, n-1)
return (x * (y.take(shift_up) - y.take(shift_down))).sum() / 2.0
要扩展三角剖分和求和三角形区域，如果您碰巧有一个凸多边形，或者您碰巧选择了一个点，该点不会生成与该多边形相交的每个其他点的线，那么这些方法就可以工作。
对于一般的非相交多边形，您需要对向量（参考点，点 a）、（参考点，点 b）的叉积求和，其中 a 和 b 彼此“相邻”。
假设您有一个按顺序定义多边形的点列表（顺序是点 i 和 i+1 形成多边形的一条线）：
Sum(叉积 ((点 0, 点 i), (点 0, 点 i + 1))，对于 i = 1 到 n - 1。
计算该叉积的大小即可得到表面积。
这将处理凹多边形，而不必担心选择一个好的参考点；生成不在多边形内的三角形的任何三个点将具有指向多边形内的任何三角形的相反方向的叉积，因此面积可以正确求和。