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. static double PoleTrojkatHeron(double a, double b, double c)
2. {
3.   double p = (a + b + c) / 2;
4.   double wynik = Math.Sqrt(p * (p - a) * (p - b) * (p - c));
5.   return wynik;
6. }

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

1. static double Odlegosc(Tuple<double, double> p1, Tuple<double, double> p2)
2. {
3.   return Math.Sqrt(Math.Pow(p1.Item1 - p2.Item1, 2) + Math.Pow(p1.Item2 - p2.Item2, 2));
4. }

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

1. static double ObliczPole(List<Tuple<double, double>> punkty)
2. {
3.   double pole = 0;
4.   for (int i = 0; i < punkty.Count - 2; i++)
5.   {
6.     double odl1 = Odlegosc(punkty[0], punkty[i + 1]);
7.     double odl2 = Odlegosc(punkty[0], punkty[i + 2]);
8.     double odl3 = Odlegosc(punkty[i + 1], punkty[i + 2]);
9.     pole += PoleTrojkatHeron(odl1, odl2, odl3);
10.   }
11.   return pole;
12. }

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. static double ObliczPole(List<Tuple<double, double>> punkty)
2. {
3.   double pole = 0;
4.   punkty.Add(punkty[0]);
5.   for (int i = 0; i < punkty.Count - 1; i++)
6.   {
7.     pole += punkty[i].Item1 * punkty[i + 1].Item2;
8.     pole -= punkty[i].Item2 * punkty[i + 1].Item1;
9.   }
10.   punkty.RemoveAt(punkty.Count - 1);
11.   return Math.Abs(pole) / 2;
12. }

Testowanie funkcji

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

1. static void Main(string[] args)
2. {
3.   Console.Write("Ile punktów ma figura?\n n = ");
4.   int n = Convert.ToInt32(Console.ReadLine());
5.   List<Tuple<double, double>> punkty = new List<Tuple<double, double>>();
6.   Console.WriteLine("Podaj punkty:");
7.   while (n-- > 0)
8.   {
9.     string[] data = Console.ReadLine().Split(' ');
10.     double x = Convert.ToDouble(data[0]);
11.     double y = Convert.ToDouble(data[1]);
12.     punkty.Add(new Tuple<double, double>(x, y));
13.   }
14.   double pole = ObliczPole(punkty);
15.   Console.WriteLine("Pole wynosi {0}", pole);
16.   Console.ReadKey();
17. }

• Kod źródłowy Implementacja