Area di un poligono#60

Area di un poligono (Editoriale)

Siano $А_{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) — i vertici di un poligono semplice (senza autointersezioni), dati nell'ordine del suo percorso in senso orario o antiorario. Allora l'area del poligono si calcola con la formula dei trapezi:

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|

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

Ogni termine della somma rappresenta l'area orientata del trapezio delimitato dal lato $A_{i} A_{i + 1}$ A_iA_{i+1}, dall'asse delle ascisse e dalle rette verticali $x = x_{i}$ x = x_i e $x = x_{i + 1}$ x = x_{i+1}. Le basi del trapezio sono $y_{i}$ y_i e $y_{i + 1}$ y_{i+1}, l'altezza è $x_{i + 1} - x_{i}$ x_{i+1} - x_i. Quando $y_{i} + y_{i + 1} > 0$ y_i + y_{i+1} > 0, l'area del trapezio è positiva se $x_{i + 1} > x_{i}$ x_{i+1} > x_i, e negativa se $x_{i + 1} < x_{i}$ x_{i+1} < x_i.

Sommando su tutti i lati, le aree delle zone esterne al poligono entrano nella somma due volte con segni opposti e si annullano a vicenda, per cui rimane solo l'area del poligono stesso. Il segno della somma dipende dalla direzione del percorso: quando il percorso è in senso orario essa è positiva, in senso antiorario è negativa. Poiché la direzione del percorso non è nota in anticipo, il risultato viene preso in valore assoluto.

Nel percorso $A \to B \to C \to D \to E \to A$ A \to B \to C \to D \to E \to A i tre lati superiori vengono percorsi da sinistra a destra, quindi i trapezi sottostanti entrano nella somma con il segno più e insieme coprono tutto lo spazio dalla spezzata $A B C D$ fino all'asse delle ascisse. I due lati inferiori vengono percorsi da destra a sinistra, e i trapezi sottostanti vengono sottratti: essi rimuovono la parte tratteggiata sotto la spezzata $D E A$ . Resta il poligono:

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}

L'area del poligono può essere calcolata anche con la formula di Surveyor (Surveyor), nota come formula di Gauss o formula del laccio (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|,

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

Sia $O (0, 0)$ O(0, 0) — l'origine delle coordinate. Allora l'area del poligono è uguale alla somma delle aree orientate dei triangoli $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. Se i vertici del triangolo $O A_{i} A_{i + 1}$ OA_iA_{i+1} sono elencati in senso antiorario, la sua area è considerata positiva; se in senso orario — negativa.

Il poligono $A_{1} A_{2} A_{3} A_{4} A_{5}$ A_1A_2A_3A_4A_5 viene percorso in senso antiorario, il punto $O$ si trova all'esterno di esso. I tre lati più lontani da $O$ danno triangoli orientati in senso antiorario: le loro aree sono positive, e insieme coprono tutto lo spazio dal punto $O$ fino alla spezzata $A_{1} A_{2} A_{3} A_{4}$ A_1A_2A_3A_4. I due lati più vicini danno triangoli orientati in senso orario: essi vengono sottratti e rimuovono l'area tratteggiata tra $O$ e la spezzata $A_{4} A_{5} A_{1}$ A_4A_5A_1. Resta il poligono:

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)

L'area orientata del triangolo $O A_{i} A_{i + 1}$ OA_iA_{i+1} è uguale alla metà del prodotto pseudoscalare dei vettori $O A_{i}$ OA_i e $O A_{i + 1}$ OA_{i+1}, cioè alla metà del determinante del secondo ordine con righe $(x_{i}, y_{i})$ (x_i, y_i) e $(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}

Implementazione dell'algoritmo

Le coordinate dei vertici del poligono vengono memorizzate negli array $x$ e $y$ :

l' $i$ -esimo vertice ha coordinate $(x [i], y [i])$ (x[i], y[i])

La dimensione degli array è maggiore di un'unità rispetto al numero massimo di vertici, poiché nella posizione $n$ viene scritta in aggiunta una copia del primo vertice.

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

La funzione findArea calcola l'area del poligono utilizzando la formula dei trapezi.

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

Per chiudere il poligono, il primo vertice viene copiato nella posizione $n$ : in questo modo il lato che collega l'ultimo vertice al primo viene elaborato nel ciclo generale senza bisogno di un controllo separato.

  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;

Il segno della somma dipende dalla direzione del percorso, quindi la funzione restituisce il suo valore assoluto.

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

Parte principale del programma. Leggiamo i dati di input.

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

Calcoliamo e stampiamo l'area del poligono.

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

Implementazione dell'algoritmo – formula di Surveyor

La funzione findArea calcola l'area del poligono utilizzando la formula di Surveyor. Le coordinate dei vertici vengono passate nei vettori $x$ e $y$ per riferimento: l' $i$ -esimo vertice ha coordinate $(x [i], y [i])$ (x[i], y[i]).

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

Per chiudere il poligono, il primo vertice viene aggiunto alla fine di entrambi i vettori: in questo modo il lato che collega l'ultimo vertice al primo viene elaborato nel ciclo generale senza bisogno di un controllo separato.

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

Dopo di che i vettori contengono $n + 1$ n + 1 elementi, quindi il ciclo viene eseguito per $i$ da $0$ a $x . s i z e () - 2$ x.size() - 2. Ad ogni iterazione viene aggiunta alla somma l'area orientata raddoppiata del triangolo $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];

Il segno della somma dipende dalla direzione del percorso, quindi la funzione restituisce la metà del suo valore assoluto.

  return fabs(s) / 2.0;
}

Dichiariamo i vettori delle coordinate.

vector<int> x, y;

Parte principale del programma. Leggiamo il numero di vertici e le loro coordinate, aggiungendo ogni vertice alla fine dei vettori.

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

C++

Calcoliamo e stampiamo l'area del poligono.

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

Implementazione dell'algoritmo – classi

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