Çoxbucaqlının sahəsi#60

Çoxbucaqlının sahəsi (Həll təhlili)

Tutaq ki, $А_{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) — sadə (özünü kəsməyən) çoxbucaqlının saat əqrəbi istiqamətində və ya əksinə istiqamətdə gəzilmə sırası ilə verilmiş təpələridir. Onda çoxbucaqlının sahəsi trapesiya düsturu ilə hesablanır:

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|

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

Cəmin hər bir həddi $A_{i} A_{i + 1}$ A_iA_{i+1} tərəfi, absis oxu və $x = x_{i}$ x = x_i və $x = x_{i + 1}$ x = x_{i+1} şaquli düz xətləri ilə məhdudlaşan trapesiyanın istiqamətləndirilmiş sahəsini təşkil edir. Trapesiyanın əsasları $y_{i}$ y_i və $y_{i + 1}$ y_{i+1}-ə, hündürlüyü isə $x_{i + 1} - x_{i}$ x_{i+1} - x_i-ə bərabərdir. $y_{i} + y_{i + 1} > 0$ y_i + y_{i+1} \gt 0 olduqda trapesiyanın sahəsi $x_{i + 1} > x_{i}$ x_{i+1} \gt x_i olduqda müsbət, $x_{i + 1} < x_{i}$ x_{i+1} \lt x_i olduqda isə mənfi olur.

Bütün tərəflər üzrə cəmləmə zamanı çoxbucaqlıdan kənarda yerləşən sahələr cəmə əks işarələrlə iki dəfə daxil olur və qarşılıqlı olaraq bir-birini aradan qaldırır, buna görə də yalnız çoxbucaqlının özünün sahəsi qalır. Cəmin işarəsi gəzilmə istiqamətindən asılıdır: saat əqrəbi istiqamətində gəzildikdə o müsbət, əksinə olduqda isə mənfidir. Gəzilmə istiqaməti əvvəlcədən məlum olmadığı üçün nəticə mütləq qiymətlə götürülür.

$A \to B \to C \to D \to E \to A$ A \to B \to C \to D \to E \to A gəzintisi zamanı üç yuxarı tərəf soldan sağa keçilir, buna görə onların altındakı trapesiyalar cəmə üstəgəl işarəsi ilə daxil olur və birlikdə $A B C D$ sınıq xəttindən absis oxuna qədər olan hər şeyi bağlayır. İki aşağı tərəf sağdan sola keçilir və onların altındakı trapesiyalar çıxılır: onlar $D E A$ sınıq xəttinin altındakı taralanmış hissəni aradan qaldırır. Nəticədə çoxbucaqlı qalır:

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}

Çoxbucaqlının sahəsini Qauss düsturu və ya bağcıq (şnurlama) düsturu kimi tanınan Sürveyer (Surveyor) düsturu ilə də tapmaq olar:

S = \frac{1}{2} i = 1 \sum n x_{i} & y_{i} x_{i + 1} & y_{i + 1} = = \frac{1}{2} x_{1} & y_{1} x_{2} & y_{2} + x_{2} & y_{2} x_{3} & y_{3} + \dots + x_{n - 1} & y_{n - 1} x_{n} & y_{n} + x_{n} & y_{n} x_{1} & 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|,

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

Tutaq ki, $O (0, 0)$ O(0, 0) — koordinat başlanğıcıdır. Onda çoxbucaqlının sahəsi $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 üçbucaqlarının istiqamətləndirilmiş sahələrinin cəminə bərabərdir. Əgər $O A_{i} A_{i + 1}$ OA_iA_{i+1} üçbucağının təpələri saat əqrəbinin əksinə sadalanıbsa, onun sahəsi müsbət, saat əqrəbi istiqamətində sadalanıbsa, mənfi hesab olunur.

$A_{1} A_{2} A_{3} A_{4} A_{5}$ A_1A_2A_3A_4A_5 çoxbucaqlısı saat əqrəbinin əksinə gəzilir, $O$ nöqtəsi isə ondan kənarda yerləşir. $O$ -dan ən uzaq olan üç tərəf saat əqrəbinin əksinə istiqamətlənmiş üçbucaqlar verir: onların sahələri müsbətdir və birlikdə $O$ nöqtəsindən $A_{1} A_{2} A_{3} A_{4}$ A_1A_2A_3A_4 sınıq xəttinə qədər olan hər şeyi bağlayır. İki yaxın tərəf isə saat əqrəbi istiqamətində yönəlmiş üçbucaqlar verir: onlar çıxılır və $O$ ilə $A_{4} A_{5} A_{1}$ A_4A_5A_1 sınıq xətti arasındakı taralanmış sahəni aradan qaldırır. Nəticədə çoxbucaqlı qalır:

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} üçbucağının istiqamətləndirilmiş sahəsi $O A_{i}$ OA_i və $O A_{i + 1}$ OA_{i+1} vektorlarının psevdoskalyar hasilinin yarısına, yəni $(x_{i}, y_{i})$ (x_i, y_i) və $(x_{i + 1}, y_{i + 1})$ (x_{i+1}, y_{i+1}) sətirlərindən ibarət ikinci tərtib determinantın yarısına bərabərdir:

S_{O A_{i} A_{i + 1}} = \frac{1}{2} x_{i} & y_{i} &1 x_{i + 1} & y_{i + 1} &1 0&0&1 = \frac{1}{2} x_{i} & y_{i} x_{i + 1} & 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}

Alqoritmin realizasiyası

Çoxbucaqlının təpələrinin koordinatlarını $x$ və $y$ massivlərində saxlayırıq:

$i$ -ci təpənin koordinatları $(x [i], y [i])$ (x[i], y[i])-dir

Massivlərin ölçüsü maksimal təpə sayından bir vahid böyükdür, çünki $n$ mövqeyinə əlavə olaraq birinci təpənin surəti yazılır.

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

findArea funksiyası çoxbucaqlının sahəsini trapesiya düsturu ilə hesablayır.

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

Çoxbucaqlını qapamaq üçün birinci təpə $n$ mövqeyinə köçürülür: bu zaman sonuncu təpəni birincisi ilə birləşdirən tərəf əlavə yoxlamaya ehtiyac olmadan ümumi dövrdə emal edilir.

  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;

Cəmin işarəsi gəzilmə istiqamətindən asılı olduğundan, funksiya onun mütləq qiymətini qaytarır.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Çoxbucaqlının sahəsini hesablayıb nəticəni çap edirik.

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

Alqoritmin realizasiyası – Sürveyer düsturu

findArea funksiyası çoxbucaqlının sahəsini Sürveyer düsturu ilə hesablayır. Təpələrin koordinatları $x$ və $y$ vektorlarına istinad vasitəsilə ötürülür: $i$ -ci təpənin koordinatları $(x [i], y [i])$ (x[i], y[i])-dir.

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

Çoxbucaqlını qapamaq üçün birinci təpə hər iki vektorun sonuna əlavə edilir: bu zaman sonuncu təpəni birincisi ilə birləşdirən tərəf əlavə yoxlamaya ehtiyac olmadan ümumi dövrdə emal edilir.

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

Bundan sonra vektorlar $n + 1$ n + 1 element saxlayır, buna görə dövr $i$ üçün $0$ -dan $x . s i z e () - 2$ x.size() - 2-yə qədər yerinə yetirilir. Hər bir iterasiyada cəmə $O A_{i} A_{i + 1}$ OA_iA_{i+1} üçbucağının ikiqat istiqamətləndirilmiş sahəsi əlavə olunur.

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

Cəmin işarəsi gəzilmə istiqamətindən asılı olduğundan, funksiya onun mütləq qiymətinin yarısını qaytarır.

  return fabs(s) / 2.0;
}

Koordinat vektorlarını elan edirik.

vector\<int\> x, y;

Proqramın əsas hissəsi. Təpələrin sayını və koordinatlarını oxuyuruq, hər bir təpəni vektorların sonuna əlavə edərək.

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

C++

Çoxbucaqlının sahəsini hesablayıb nəticəni çap edirik.

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

Alqoritmin realizasiyası – siniflər

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