minimalny obrys wypukły

Obiekty i przekształcenia geometryczne, opisane za pomocą układu (nie zawsze prostokątnego) współrzędnych.
michal_b
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 16 sty 2008, o 20:07
Płeć: Mężczyzna
Lokalizacja: warszawa

minimalny obrys wypukły

Post autor: michal_b » 17 sty 2008, o 14:17

JAk znaleść minimalny obrys wypukły punktów na płaszczyznie, co to jest wogóle ten minimalny obrys wypukły ?

Awatar użytkownika
Szemek
Gość Specjalny
Gość Specjalny
Posty: 4819
Rejestracja: 10 paź 2006, o 23:03
Płeć: Mężczyzna
Lokalizacja: Gdańsk

minimalny obrys wypukły

Post autor: Szemek » 17 sty 2008, o 14:33

poszukaj w sieci pojęcia: otoczka wypukła -> http://pl.wikipedia.org/wiki/Otoczka_wypuk%C5%82a Algorytm Grahama Algorytm Jarvisa [ Dodano: 17 Stycznia 2008, 14:34 ] i algorytm przyrostowy

michal_b
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 16 sty 2008, o 20:07
Płeć: Mężczyzna
Lokalizacja: warszawa

minimalny obrys wypukły

Post autor: michal_b » 17 sty 2008, o 15:07

dzieki, tylko jeszcze musze to użyć w c++....

Awatar użytkownika
Szemek
Gość Specjalny
Gość Specjalny
Posty: 4819
Rejestracja: 10 paź 2006, o 23:03
Płeć: Mężczyzna
Lokalizacja: Gdańsk

minimalny obrys wypukły

Post autor: Szemek » 17 sty 2008, o 15:52

odpowiednie zapytanie w google i da się znaleźć nawet pełną implementację w C++

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6695
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E

minimalny obrys wypukły

Post autor: mariuszm » 25 lut 2009, o 09:59

Implementację algorytmu grahama znajdziesz na stronie Kamila Deryńskiego http://files.derynski.net/moje_prace/graham.c

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6695
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E

Re: minimalny obrys wypukły

Post autor: mariuszm » 20 wrz 2017, o 10:48

Jeśli chodzi o algorytm Grahama to pseudokod jest u Cormena i reszty

Kod: Zaznacz cały

1 let p0 be the point in Q with the minimum y-coordinate,
        or the leftmost such point in case of a tie
2 let <p1,p2,...,pm> be the remaining points in Q
        sorted by polar angle in counterclockwise order around p0
        (if more than one point has the same angle remove all but
         the one that is farthest from p0)
3 let S be an empty stack
4 PUSH(p0,S)
5 PUSH(p1,S)
6 PUSH(p2,S)
7 for i:=3 to m do
8      while the angle formed by points NEXT-TO-TOP(S),TOP(S)
               and p1 makes a nonleft turn do
9            POP(S)
10     PUSH(pi,S)
11  return S
Na ważniaku widziałem próbę przetłumaczenia tego pseudokodu
na polski ale mam wątpliwości co do poprawności tego tłumaczenia

ODPOWIEDZ