wypuklość wielokata
: 11 maja 2011, 08:10
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.
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.