计算任意多边形面积

乍一听,计算面积不应该是手到擒来的事嘛,其实仔细一想还真不是。多边形是凸的还好说,那非凸的多边形怎么算嘛,难道要把它三角化,再把三角形的面积累加? 这时候就有神人提出了 鞋带算法(shoelace algorithm)

原理

具体的原理我不做赘述,附上几个链接,有兴趣的同学可以深入了解一下:

实现

  • C++

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // Get area of any polygon
    double get_polygon_area(const std::vector<Point_2>& points_2d)
    {
    int n = points_2d.size();
    double area = 0.0;

    // Calculate value of shoelace formula
    int j = n - 1;
    for (int i = 0; i < n; i++)
    {
    const auto& pt_i = points_2d[i];
    const auto& pt_j = points_2d[j];
    area += (pt_j.x() + pt_i.x()) * (pt_j.y() - pt_i.y());
    j = i; // j is previous vertex to i
    }

    // Return absolute value
    return abs(area / 2.0);
    }
  • GeeksforGeeks给出的多语言实现:Area of a polygon with given n ordered vertices

神人

那这个提出鞋带算法的神人是谁呢?1795年的 Carl Friedrich Gauss