minimalny obrys wypukły
-
- Użytkownik
- Posty: 5
- Rejestracja: 16 sty 2008, o 20:07
- Płeć: Mężczyzna
- Lokalizacja: warszawa
minimalny obrys wypukły
JAk znaleść minimalny obrys wypukły punktów na płaszczyznie, co to jest wogóle ten minimalny obrys wypukły ?
- Szemek
- 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
poszukaj w sieci pojęcia:
otoczka wypukła ->
Algorytm Grahama
Algorytm Jarvisa
[ Dodano: 17 Stycznia 2008, 14:34 ]
i algorytm przyrostowy
otoczka wypukła ->
Algorytm Grahama
Algorytm Jarvisa
[ Dodano: 17 Stycznia 2008, 14:34 ]
i algorytm przyrostowy
- Mariusz M
- 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
Implementację algorytmu grahama znajdziesz na stronie Kamila Deryńskiego
Kod: Zaznacz cały
http://files.derynski.net/moje_prace/graham.c
- Mariusz M
- 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
Jeśli chodzi o algorytm Grahama to pseudokod jest u Cormena i reszty
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
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 polski ale mam wątpliwości co do poprawności tego tłumaczenia