Area of a Polygon#60

Area of a Polygon (Editorial)

Let $А_{1} (x_{1}, y_{1}), А_{2} (x_{2}, y_{2}), ..., А_{n} (x_{n}, y_{n})$ А_1(x_1, y_1), А_2(x_2, y_2), ..., А_n(x_n, y_n) be the vertices of a simple (non-self-intersecting) polygon, listed in clockwise or counterclockwise order. Then the area of the polygon is given by the trapezoid formula:

S = i = 1 \sum n \frac{y _{i + 1} + y _{i}}{2} (x_{i + 1} - x_{i})

S = \left| \sum_{i=1}^{n} \frac{y_{i+1} + y_i}{2} (x_{i+1} - x_i) \right|

where $А_{n + 1} (x_{n + 1}, y_{n + 1} = А_{1} (x_{1}, y_{1})$ А_{n+1}(x_{n+1}, y_{n+1} = А_1(x_1, y_1).

Each term of the sum is the signed area of the trapezoid bounded by the side $A_{i} A_{i + 1}$ A_iA_{i+1}, the $x$ -axis, and the vertical lines $x = x_{i}$ x = x_i and $x = x_{i + 1}$ x = x_{i+1}. The bases of the trapezoid are $y_{i}$ y_i and $y_{i + 1}$ y_{i+1}, and its height is $x_{i + 1} - x_{i}$ x_{i+1} - x_i. When $y_{i} + y_{i + 1} > 0$ y_i + y_{i+1} > 0, the area of the trapezoid is positive if $x_{i + 1} > x_{i}$ x_{i+1} > x_i and negative if $x_{i + 1} < x_{i}$ x_{i+1} < x_i.

When the terms are summed over all sides, the areas of the regions lying outside the polygon enter the sum twice with opposite signs and cancel out, so only the area of the polygon itself remains. The sign of the sum depends on the direction of traversal: it is positive for a clockwise traversal and negative for a counterclockwise one. Since the direction of traversal is not known in advance, the absolute value of the result is taken.

In the traversal $A \to B \to C \to D \to E \to A$ A \to B \to C \to D \to E \to A, the three upper sides are traversed from left to right, so the trapezoids beneath them enter the sum with a plus sign and together cover the entire region between the polyline $A B C D$ and the $x$ -axis. The two lower sides are traversed from right to left, and the trapezoids beneath them are subtracted: they remove the hatched region under the polyline $D E A$ . What remains is the polygon:

S_{A B C D E} = S_{A B B_{1} A_{1}} + S_{B C C_{1} B_{1}} + S_{C D D_{1} C_{1}} - S_{D E E_{1} D_{1}} - S_{E A A_{1} E_{1}}

S_{ABCDE} = S_{ABB_1A_1} + S_{BCC_1B_1} + S_{CDD_1C_1} – S_{DEE_1D_1} – S_{EAA_1E_1}

The area of a polygon can also be found using the Surveyor's formula, also known as Gauss’s area formula or the shoelace formula:

S = \frac{1}{2} i = 1 \sum n x_{i} x_{i + 1} y_{i} y_{i + 1} = = \frac{1}{2} x_{1} x_{2} y_{1} y_{2} + x_{2} x_{3} y_{2} y_{3} + \dots + x_{n - 1} x_{n} y_{n - 1} y_{n} + x_{n} x_{1} y_{n} y_{1},

S = \frac{1}{2} \left| \sum_{i=1}^{n} \begin{vmatrix} x_i & y_i \\ x_{i+1} & y_{i+1} \end{vmatrix} \right| = \\ = \frac{1}{2} \left| \begin{vmatrix} x_1 & y_1 \\ x_2 & y_2 \end{vmatrix} + \begin{vmatrix} x_2 & y_2 \\ x_3 & y_3 \end{vmatrix} + \ldots + \begin{vmatrix} x_{n-1} & y_{n-1} \\ x_n & y_n \end{vmatrix} + \begin{vmatrix} x_n & y_n \\ x_1 & y_1 \end{vmatrix} \right|,

where $А_{n + 1} (x_{n + 1}, y_{n + 1}) = А_{1} (x_{1}, y_{1})$ А_{n+1}(x_{n+1}, y_{n+1}) = А_1(x_1, y_1).

Let $O (0, 0)$ O(0, 0) be the origin. Then the area of the polygon equals the sum of the signed areas of the triangles $O A_{1} A_{2}, O A_{2} A_{3}, O A_{3} A_{4}, ..., O A_{n} A_{1}$ OA_1A_2, OA_2A_3, OA_3A_4, ..., OA_nA_1. If the vertices of the triangle $O A_{i} A_{i + 1}$ OA_iA_{i+1} are listed in counterclockwise order, its area is considered positive; if they are listed in clockwise order, it is considered negative.

The polygon $A_{1} A_{2} A_{3} A_{4} A_{5}$ A_1A_2A_3A_4A_5 is traversed counterclockwise, and the point $O$ lies outside it. The three sides farthest from $O$ give counterclockwise-oriented triangles: their areas are positive, and together they cover the entire region between the point $O$ and the polyline $A_{1} A_{2} A_{3} A_{4}$ A_1A_2A_3A_4. The two nearest sides give clockwise-oriented triangles: these are subtracted and remove the hatched region between $O$ and the polyline $A_{4} A_{5} A_{1}$ A_4A_5A_1. What remains is the polygon:

S (A_{1} A_{2} A_{3} A_{4} A_{5}) = S (O A_{1} A_{2}) + S (O A_{2} A_{3}) + S (O A_{3} A_{4}) - S (O A_{4} A_{5}) - S (O A_{5} A_{1})

S(A_1A_2A_3A_4A_5) = S(OA_1A_2) + S(OA_2A_3) + S(OA_3A_4) - S(OA_4A_5) − S(OA_5A_1)

The signed area of the triangle $O A_{i} A_{i + 1}$ OA_iA_{i+1} equals half the cross product of the vectors $O A_{i}$ OA_i and $O A_{i + 1}$ OA_{i+1}, that is, half the second-order determinant with rows $(x_{i}, y_{i})$ (x_i, y_i) and $(x_{i + 1}, y_{i + 1})$ (x_{i+1}, y_{i+1}):

S_{O A_{i} A_{i + 1}} = \frac{1}{2} x_{i} x_{i + 1} 0 y_{i} y_{i + 1} 0 111 = \frac{1}{2} x_{i} x_{i + 1} y_{i} y_{i + 1}

S_{OA_iA_{i+1}} = \frac{1}{2} \begin{vmatrix} x_i & y_i & 1 \\ x_{i+1} & y_{i+1} & 1 \\ 0 & 0 & 1 \end{vmatrix} = \frac{1}{2} \begin{vmatrix} x_i & y_i \\ x_{i+1} & y_{i+1} \end{vmatrix}

Algorithm implementation

We store the coordinates of the polygon's vertices in the arrays $x$ and $y$ :

the $i$ -th vertex has coordinates $(x [i], y [i])$ (x[i], y[i])

The size of the arrays is one greater than the maximum number of vertices, since a copy of the first vertex is additionally stored at position $n$ .

#define MAX 1002
int x[MAX], y[MAX];

The function findArea computes the area of the polygon using the trapezoid formula.

double findArea(int *x, int *y)
{
  double s = 0;

To close the polygon, the first vertex is copied to position $n$ : this way, the side connecting the last vertex to the first is handled in the main loop without a separate check.

  x[n] = x[0]; y[n] = y[0];
  for(int i = 0; i < n; i++)
    s += (y[i+1] + y[i]) * (x[i+1] - x[i]) / 2.0;

The sign of the sum depends on the direction of traversal, so the function returns its absolute value.

  return (s < 0) ? -s : s;
}

The main part of the program. Read the input data.

scanf("%d",&n);
for(i = 0; i < n; i++)
  scanf("%d %d",&x[i],&y[i]);

Compute and print the area of the polygon.

printf("%.3lf\n",findArea(x,y));

Algorithm implementation – the Surveyor's formula

The function findArea computes the area of the polygon using the Surveyor's formula. The vertex coordinates are passed in the vectors $x$ and $y$ by reference: the $i$ -th vertex has coordinates $(x [i], y [i])$ (x[i], y[i]).

double findArea(vector<int> &x, vector<int> &y)
{
  double s = 0;

To close the polygon, the first vertex is appended to the end of both vectors: this way, the side connecting the last vertex to the first is handled in the main loop without a separate check.

  x.push_back(x[0]); y.push_back(y[0]);

After that, the vectors contain $n + 1$ n + 1 elements, so the loop runs for $i$ from $0$ to $x . s i z e () - 2$ x.size() - 2. At each iteration, twice the signed area of the triangle $O A_{i} A_{i + 1}$ OA_iA_{i+1} is added to the sum.

  for (int i = 0; i < x.size() - 1; i++)
    s += y[i+1] * x[i] - y[i] * x[i+1];

The sign of the sum depends on the direction of traversal, so the function returns half of its absolute value.

  return fabs(s) / 2.0;
}

Declare the coordinate vectors.

vector<int> x, y;

The main part of the program. Read the number of vertices and their coordinates, appending each vertex to the end of the vectors.

scanf("%d",&n);
for(i = 0; i < n; i++)
{
  scanf("%d %d",&a,&b);
  x.push_back(a);
  y.push_back(b);
}

C++

Compute and print the area of the polygon.

printf("%.3lf\n",findArea(x,y));

Algorithm implementation – classes

#include <stdio.h>

class Point
{
private:
  double x, y;
public:
  Point(double x = 0, double y = 0) : x(x), y(y) {};
  double GetX()
  {
    return x;
  }
  double GetY()
  {
    return y;
  }
  // cross product
  double operator* (const Point &p)
  {
    return this->x * p.y - this->y * p.x;
  }
};

class Shape
{
protected:
  Point *p;
  int size;
public:
  Shape(int size = 0) : size(size)
  {
    p = new Point[size+1];
  }
  ~Shape()
  {
    delete[] p;
  }
};

class Polygon : public Shape
{
public:
  Polygon(int n = 0) : Shape(n)  {};

  void ReadPoints(void)
  {
    double x, y;
    for(int i = 0; i < size; i++)
    {
      scanf("%lf %lf",&x,&y);
      p[i] = Point(x,y);
    }
    p[size] = p[0];
  }

  double Area(void)
  {
    double s = 0;
    for(int i = 0; i < size; i++)
      s += p[i] * p[i+1];
    return (s < 0) ? -s/2 : s/2;
  }
};

int n;

int main(void)
{
  scanf("%d",&n);
  Polygon p(n);
  p.ReadPoints();
  printf("%.3lf\n",p.Area());
  return 0;
}

C++