Strona główna » Algorytmy » Artykuły » Pole Wypukłej Figury
 

Pole Wypukłej Figury

https://mattomatti.com/a0272

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:

C++C#
Python
  1. def PoleTrojkatHeron(a, b, c):
  2.   p = (a + b + c) / 2
  3.   wynik = math.sqrt(p * (p - a) * (p - b) * (p - c))
  4.   return wynik

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

C++C#
Python
  1. def Odlegosc(p1, p2):
  2.   return math.sqrt(math.pow(p1[0] - p2[0], 2) + math.pow(p1[1] - p2[1], 2))

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

C++C#
Python
  1. def ObliczPole(punkty):
  2.   pole = 0
  3.   for i in range(len(punkty) - 2):
  4.     odl1 = Odlegosc(punkty[0], punkty[i + 1])
  5.     odl2 = Odlegosc(punkty[0], punkty[i + 2])
  6.     odl3 = Odlegosc(punkty[i + 1], punkty[i + 2])
  7.     pole += PoleTrojkatHeron(odl1, odl2, odl3)
  8.   return pole

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 = |x1y2 - x2y1 + x2y3 - x3y2 + ... + xny1 - x1yn| / 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.

C++C#
Python
  1. def ObliczPole(punkty):
  2.   pole = 0
  3.   punkty.append(punkty[0])
  4.   for i in range(len(punkty) - 1):
  5.     pole += punkty[i][0] * punkty[i + 1][1]
  6.     pole -= punkty[i][1] * punkty[i + 1][0]
  7.   punkty.pop()
  8.   return abs(pole) / 2

Testowanie funkcji

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

C++C#
Python
  1. n = int(input("Ile punktów ma figura?\n n = "))
  2. punkty = []
  3. print("Podaj punkty:")
  4. for i in range(n):
  5.   data = input().split(' ')
  6.   x = float(data[0])
  7.   y = float(data[1])
  8.   punkty.append((x, y))
  9. pole = ObliczPole(punkty)
  10. print("Pole wynosi", pole)