问题

计算任意多边形的的面积

基本的要求是:

  • 理论上任意个顶点
  • 凹凸不分
  • 给出的顶点集合是按照逆时针或者顺时针的顺序排列好
  • 输出为多边形的面积S

算法思想

直接计算多边形的面积有困难,想到任何一个多边形都可以被分割为若干个三角形。
三角形的面积好计算,若干个三角形面积求和即可得到多边形的面积。
S = S1+S2+S3+...+Sn

三角形的坐标计算面积公式:

1.0

S = 1/2*(ad+cf+eb-af-cb-de)
说明:这里的S可能为正,也可能为负,取决于三角形顶点坐标的方向。这里不取绝对值才能够在凹多边形的情况下正确。

算法描述:

  1. 选取出发顶点k(一般是0)
  2. 计算以(k,i+1,i+2)为顶点的三角形面积(面积可以为负)
  3. 多边形面积加三角形面积赋值为多边形面积
  4. 重复2.3.直到i等于顶点数-1
  5. 输出多边形面积

主要代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# coding:utf-8
ploy = [(0,2),(0,0),(2,0),(0.5,0.5)]

# @parame
# points = 三角形顶点数组
def trangleS(points):
p1 = points[0]
p2 = points[1]
p3 = points[2]
S = (1.0/2)*(p1[0]*p2[1]+p2[0]*p3[1]+p3[0]*p1[1]-p1[0]*p3[1]-p2[0]*p1[1]-p3[0]*p2[1])
return S

# @parame
# points = 多边形顶点数组
def polyS(points):
pointN = len(points)
S = 0
for i in range(1,pointN-1):
point = [1,2,3]
point[0] = points[0]
point[1] = points[i]
point[2] = points[(i+1)%pointN];
S +=trangleS(point)
return S

print polyS(ploy)

参考

https://www.cnblogs.com/TenosDoIt/p/4047211.html
https://baike.baidu.com/item/三角形面积公式/8491990?fr=aladdin