wypuklość wielokata

Pytania o rozwiązania zadań.
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Cobalt
Witam na forum
Witam na forum
Posty: 1
Rejestracja: 11 maja 2011, 08:01
Płeć:

wypuklość wielokata

Post autor: Cobalt »

Witam,

Otrzymałem taki projekt

Danych jest n punktów P1,P2,…Pn, oznaczających wierzchołki pewnego wielokąta. Punkty są wymienione w kolejności położenia na obwodzie tego wielokąta. Porównaj metody badania wypukłości zadanego wielokąta.

I oto rozwiązanie:

Zastosowane zostały dwie metody sprawdzania wypukłości wielokąta. Pierwsza polega na badaniu współliniowości trzech kolejnych punktów. Druga sprawdza przy pomocy trójkątów tworzonych przez każde trzy punkty zadanego wielokąta czy, któryś z pozostałych punktów zawiera się w polu przez nie tworzonym. Jeżeli tak oznacza to również, że zawiera się w polu wielokąta wypukłego, więc wielokąt utworzony z wykorzystaniem tego punktu nie może być wypukły. Metoda opierająca się na współliniowości punktów ma złożoność liniową, natomiast opierająca się na badaniu trójkątów n^3.

Mógłbym prosić was o wytłumaczenie tego rozwiązania najlepiej na przykładzie.
ODPOWIEDZ