Площа многокутника#60

Площа многокутника (Розбір)

Нехай $А_{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) — вершини простого (без самоперетинів) многокутника, задані в порядку його обходу за годинниковою стрілкою або проти неї. Тоді площа многокутника обчислюється за формулою трапецій:

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|

де $А_{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).

Кожен доданок суми являє собою орієнтовану площу трапеції, обмеженої стороною $A_{i} A_{i + 1}$ A_iA_{i+1}, віссю абсцис та вертикальними прямими $x = x_{i}$ x = x_i і $x = x_{i + 1}$ x = x_{i+1}. Основи трапеції дорівнюють $y_{i}$ y_i та $y_{i + 1}$ y_{i+1}, висота дорівнює $x_{i + 1} - x_{i}$ x_{i+1} - x_i. При $y_{i} + y_{i + 1} > 0$ y_i + y_{i+1} > 0 площа трапеції додатна, якщо $x_{i + 1} > x_{i}$ x_{i+1} > x_i, і від'ємна, якщо $x_{i + 1} < x_{i}$ x_{i+1} < x_i.

При підсумовуванні по всіх сторонах площі ділянок, що лежать поза многокутником, входять до суми двічі з протилежними знаками і взаємно знищуються, тому залишається тільки площа самого многокутника. Знак суми залежить від напрямку обходу: при обході за годинниковою стрілкою вона додатна, проти годинникової стрілки — від'ємна. Оскільки напрямок обходу заздалегідь невідомий, результат береться за модулем.

При обході $A \to B \to C \to D \to E \to A$ A \to B \to C \to D \to E \to A три верхні сторони проходяться зліва направо, тому трапеції під ними входять до суми з плюсом і разом закривають усе від ламаної $A B C D$ до осі абсцис. Дві нижні сторони проходяться справа наліво, і трапеції під ними віднімаються: вони прибирають заштриховану частину під ламаною $D E A$ . Залишається многокутник:

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}

Площу многокутника можна також знайти за формулою Сюрвейора (Surveyor), відомою як формула Гаусса або формула шнурування:

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|,

де $А_{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).

Нехай $O (0, 0)$ O(0, 0) — центр координат. Тоді площа многокутника дорівнює сумі орієнтованих площ трикутників $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. Якщо вершини трикутника $O A_{i} A_{i + 1}$ OA_iA_{i+1} перелічені проти годинникової стрілки, його площа вважається додатною, якщо за годинниковою стрілкою — від'ємною.

Многокутник $A_{1} A_{2} A_{3} A_{4} A_{5}$ A_1A_2A_3A_4A_5 обходиться проти годинникової стрілки, точка $O$ лежить поза ним. Три найдальші від $O$ сторони дають трикутники, орієнтовані проти годинникової стрілки: їхні площі додатні, і разом вони закривають усе від точки $O$ до ламаної $A_{1} A_{2} A_{3} A_{4}$ A_1A_2A_3A_4. Дві найближчі сторони дають трикутники, орієнтовані за годинниковою стрілкою: вони віднімаються і прибирають заштриховану область між $O$ та ламаною $A_{4} A_{5} A_{1}$ A_4A_5A_1. Залишається многокутник:

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)

Орієнтована площа трикутника $O A_{i} A_{i + 1}$ OA_iA_{i+1} дорівнює половині псевдоскалярного добутку векторів $O A_{i}$ OA_i та $O A_{i + 1}$ OA_{i+1}, тобто половині визначника другого порядку з рядками $(x_{i}, y_{i})$ (x_i, y_i) і $(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}

Реалізація алгоритму

Координати вершин многокутника зберігаємо в масивах $x$ та $y$ :

$i$ -та вершина має координати $(x [i], y [i])$ (x[i], y[i])

Розмір масивів на одиницю більший за максимальну кількість вершин, оскільки в позицію $n$ додатково записується копія першої вершини.

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

Функція findArea обчислює площу многокутника за формулою трапецій.

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

Щоб замкнути многокутник, перша вершина копіюється в позицію $n$ : тоді сторона, що з'єднує останню вершину з першою, обробляється в загальному циклі без окремої перевірки.

  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;

Знак суми залежить від напрямку обходу, тому функція повертає її модуль.

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

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо та виводимо площу многокутника.

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

Реалізація алгоритму – формула Сюрвейора

Функція findArea обчислює площу многокутника за формулою Сюрвейора. Координати вершин передаються у векторах $x$ та $y$ за посиланням: $i$ -та вершина має координати $(x [i], y [i])$ (x[i], y[i]).

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

Щоб замкнути многокутник, перша вершина дописується в кінець обох векторів: тоді сторона, що з'єднує останню вершину з першою, обробляється в загальному циклі без окремої перевірки.

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

Після цього вектори містять $n + 1$ n + 1 елемент, тому цикл виконується для $i$ від $0$ до $x . s i z e () - 2$ x.size() - 2. На кожній ітерації до суми додається подвоєна орієнтована площа трикутника $O A_{i} A_{i + 1}$ OA_iA_{i+1}.

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

Знак суми залежить від напрямку обходу, тому функція повертає половину її модуля.

  return fabs(s) / 2.0;
}

Оголошуємо вектори координат.

vector<int> x, y;

Основна частина програми. Читаємо кількість вершин та їхні координати, додаючи кожну вершину в кінець векторів.

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

C++

Обчислюємо та виводимо площу многокутника.

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

Реалізація алгоритму – класи

#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++