Pole Wypukłej Figury

Cel

Najprostszym sposobem na policzenie pola dowolnej, wypukłej figury jest podzielenie jej na trójkąty. Nie jest to jednak metoda optymalna, ponieważ wykonuje wiele obliczeń. W tym artykule zostanie podany wzór, który pozwala bardzo szybko obliczyć pole dla dowolnej figury.

Przykład

Przykładowo do obliczenia będzie następująca figura:

W tym przypadku pole figury wynosi 7. Program nie będzie miał jednak narysowanej figury, a jedynie podane punkty, więc trzeba napisać algorytm, który na ich podstawie obliczy szukaną wartość.

Implementacja

Na trójkąty

Jednym ze sposobów jest podział figury na trójkąty. W tym celu można np. wybrać jeden punkt jako początkowy, a następnie wybierać pary kolejnych wierzchołków z pozostałych i dla każdego oddzielnie policzyć pole. Suma takich pól da pole powierzchni całej figury. Oto przykładowy podział figury:

W podanym powyżej przykładzie punktem głównym jest A, a cała figura została podzielona na trójkąty ABC oraz ACD. Oczywiście innym sposobem byłoby wybranie punktu środkowego trójkąta tj. średnią arytmetyczną jego punktów, ale wtedy figura byłaby podzielona nie na n-2 trójkąty, a na n, gdzie n to ilość boków trójkąta.

Pole trójkąta można policzyć ze wzoru Herona:

1. float PoleTrojkatHeron(float a, float b, float c) {
2.   float p = (a + b + c) / 2;
3.   float wynik = sqrt(p*(p - a)*(p - b)*(p - c));
4.   return wynik;
5. }

Należy jednak znać wtedy odległości pomiędzy punktami, które można obliczyć następująco:

1. float Odlegosc(pair<float, float> p1, pair<float, float> p2) {
2.   return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
3. }

Używając powyższych funkcji możliwe jest teraz napisanie kodu, który oblicz pole powierzchni dla figury,

1. float ObliczPole(vector<pair<float, float>> punkty) {
2.   float pole = 0;
3.   for (int i = 0; i < punkty.size() - 2; i++) {
4.     float odl1 = Odlegosc(punkty[0], punkty[i + 1]);
5.     float odl2 = Odlegosc(punkty[0], punkty[i + 2]);
6.     float odl3 = Odlegosc(punkty[i + 1], punkty[i + 2]);
7.     pole += PoleTrojkatHeron(odl1, odl2, odl3);
8.   }
9.   return pole;
10. }

Podany wyżej algorytm ma wysoką złożoność, ponieważ odległości od punktu głównego do pozostałego jest zawsze wyliczana dwa razy (jedną odległość można obliczyć do dwóch trójkątów). Ponadto metoda Odleglosc() oraz PoleTrojkatHeron() korzystają z operacji pierwiastkowania, która znacząco wpływa na wydajność programu.

Ze wzoru

Pole figury można jednak obliczyć znacznie prościej korzystając z następującego wzoru:

P = |x₁y₂ - x₂y₁ + x₂y₃ - x₃y₂ + ... + x_ny₁ - x₁y_n| / 2

Wtedy kod można uprościć do podstawowych operacji arytmetycznych: dodawania, odejmowania i mnożenia. W poniższym kodzie w celu uniknięcia operacji modulo pierwszy element jest dodawany na koniec listy, a na koniec usuwany.

1. float ObliczPole(vector<pair<float, float>> punkty) {
2.   float pole = 0;
3.   punkty.push_back(punkty[0]);
4.   for (int i = 0; i < punkty.size() - 1; i++) {
5.     pole += punkty[i].first * punkty[i + 1].second;
6.     pole -= punkty[i].second * punkty[i + 1].first;
7.   }
8.   punkty.pop_back();
9.   return abs(pole) / 2;
10. }

Testowanie funkcji

Do przetestowania napisanych funkcji można skorzystać z poniższego fragmentu kodu:

1. int main() {
2.   int n;
3.   float x, y;
4.   cout << "Ile punktow ma figura?\n n = ";
5.   cin >> n;
6.   vector<pair<float, float>> punkty;
7.   cout << "Podaj punkty:" << endl;
8.   while (n-- > 0) {
9.     cin >> x >> y;
10.     punkty.push_back(make_pair(x, y));
11.   }
12.   float pole = ObliczPole(punkty);
13.   cout << "Pole wynosi " << pole;
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja