logo标签列表

如何计算二维多边形的面积？

algorithmgeometry2d
102
假设在二维空间中有一系列不相交的点，如何有效地确定形成的多边形的面积？
值得注意的是，这不是作业，我也不在寻找代码。我希望找到一种方法的描述，以便能实现自己的方法。我有一些想法，比如从点集合中获取三角形序列，但是我知道对于凸多边形和凹多边形之类的特殊情况可能会出现问题。
6
“表面积”这个术语有点误导。你似乎只想要普通的面积。在三维空间中，“表面积”是指外部表面的面积，因此该概念的自然二维推广应该是多边形周长的长度，显然不是你要找的东西。 - batty
1
def area(polygon): return abs(numpy.cross(polygon, numpy.roll(polygon, -1, 0)).sum() / 2) - iouvxz
16个回答
1

与语言无关的解决方案：

假设：一个多边形总是可以由n-2个不重叠的三角形组成（n=点或边的数量）。1个三角形=3边形=1个三角形；1个正方形=4边形=2个三角形；等等。QED

因此，一个多边形可以通过“削减”三角形来缩小，总面积将是这些三角形面积的总和。用一张纸和剪刀试试，最好在跟随之前能够想象出这个过程。

如果你在多边形路径中取任意3个连续点，并用这些点创建一个三角形，你将只有三种可能的情况之一：

  1. 结果三角形完全在原多边形内部
  2. 结果三角形完全在原多边形外部
  3. 结果三角形部分包含在原多边形内部

我们只对第一种情况感兴趣（完全包含的情况）。

每次我们发现其中之一时，我们就将其削减，计算其面积（公式很简单，这里不再解释），并制作一个边少一个的新多边形（相当于去掉这个三角形的多边形）。直到只剩下一个三角形。

如何以编程方式实现：

创建一个由（连续的）点组成的数组，表示多边形周围的路径。从点0开始。运行该数组，从点x、x+1和x+2制作三角形（一次一个）。将每个三角形从形状转换为区域，并将其与从多边形创建的区域相交。如果结果交集与原始三角形相同，则该三角形完全包含在多边形中，可以被切掉。从数组中删除x+1并从x=0重新开始。否则（如果三角形在多边形外部[部分或完全]），移动到数组中的下一个点x+1。

此外，如果您想要与地图集成并从地理点开始，则必须首先将其从地理点转换为屏幕点。这需要决定地球形状的建模和公式（尽管我们倾向于认为地球是一个球体，但它实际上是一个不规则的卵形，有凹痕）。有许多模型可用，有关更多信息，请参见维基百科。一个重要问题是是否将该区域视为平面还是曲面。通常，“小”区域，其中点之间的距离最多为几公里，如果考虑平面而不是凸面，则不会产生显着误差。

1
在笛卡尔空间中，比求和三角形更好的方法是求和梯形：
area = 0;
for (i = 0; i < n; i++) {
  i1 = (i + 1) % n;
  area += (vertex[i].y + vertex[i1].y) * (vertex[i1].x - vertex[i].x) / 2.0;
}
0

我的倾向是简单地开始切割三角形。我不认为其他任何方法都能避免变得非常复杂。

取组成多边形的三个连续点。确保角度小于180度。现在你有一个新的三角形，应该很容易计算，从多边形的点列表中删除中间点。重复此过程，直到只剩下三个点。

这个问题的棘手之处在于，如果你的三个连续点定义了一个在多边形外部或部分外部的三角形，那么你就会遇到问题。 - Richard
@Richard：这就是为什么资格要求180度的原因。如果你切掉多边形外面的三角形，你最终会得到太多的度数。 - Loren Pechtel
你可能需要更好地描述如何找到角度。在平面几何中，三个点作为三角形的一部分，任何角度或角度组合都不可能超过180度 - 检查似乎是毫无意义的。 - Richard
@Richard：在你的多边形上，每个交点都有一个角度。如果相关的三角形位于多边形外部，则两条线段之间的夹角将大于180度。 - Loren Pechtel
你的意思是相邻两条边的内角大于180度。 - Richard
是的 - 我正在从多边形内部查看角度。如果潜在的三角形实际上位于多边形外部，则从这个角度来看，你将有三个大于180度的角度。不过，测试第一个角度就足够了。 - Loren Pechtel
0
我将提供一些简单的函数来计算二维多边形的面积。这适用于凸多边形和凹多边形。我们只需要将多边形分成许多子三角形即可。
//don't forget to include cmath for abs function
struct Point{
  double x;
  double y;
}
// cross_product
double cp(Point a, Point b){ //returns cross product
  return a.x*b.y-a.y*b.x;
}

double area(Point * vertices, int n){  //n is number of sides
  double sum=0.0;
  for(i=0; i<n; i++){
    sum+=cp(vertices[i], vertices[(i+1)%n]); //%n is for last triangle
  }
  return abs(sum)/2.0;
}
-1

Python 代码

如此描述：http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

使用 pandas

import pandas as pd

df = pd.DataFrame({'x': [10, 20, 20, 30, 20, 10, 0], 'y': [-10, -10, -10, 0, 10, 30, 20]})
df = df.append(df.loc[0])

first_product = (df['x'].shift(1) * df['y']).fillna(0).sum()
second_product = (df['y'].shift(1) * df['x']).fillna(0).sum()

(first_product - second_product) / 2
600
-1

C语言实现方法：

float areaForPoly(const int numVerts, const Point *verts)
{
    Point v2;
    float area = 0.0f;

    for (int i = 0; i<numVerts; i++){
        v2 = verts[(i + 1) % numVerts];
        area += verts[i].x*v2.y - verts[i].y*v2.x;
    }

    return area / 2.0f;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接