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 »

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
Użytkownik
Użytkownik
Posty: 4819
Rejestracja: 10 paź 2006, o 23:03
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 43 razy
Pomógł: 1407 razy

minimalny obrys wypukły

Post autor: Szemek »

poszukaj w sieci pojęcia:
otoczka wypukła ->
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 »

dzieki, tylko jeszcze musze to użyć w c++....
Awatar użytkownika
Szemek
Użytkownik
Użytkownik
Posty: 4819
Rejestracja: 10 paź 2006, o 23:03
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 43 razy
Pomógł: 1407 razy

minimalny obrys wypukły

Post autor: Szemek »

odpowiednie zapytanie w google i da się znaleźć nawet pełną implementację w C++
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

minimalny obrys wypukły

Post autor: Mariusz M »

Implementację algorytmu grahama znajdziesz na stronie Kamila Deryńskiego

Kod: Zaznacz cały

http://files.derynski.net/moje_prace/graham.c
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Re: minimalny obrys wypukły

Post autor: Mariusz M »

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