algorytm.org

Szukaj

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Porządkowanie wierzchołków wg rosnących kątów nachylenia ich wektorów wodzących
Ocena użytkowników:***** / 16
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 03 sierpnia 2005 22:34

Czasami zdarza się, że mamy pewien zbiór wierzchołków i musimy go uporządkować względem rosnących kątów nachylenia ich wektorów wodzących do osi OX. Taki porządek jest wykorzystywany np. przy konstrukcji wypukłej otoczki.
Istnieje metoda sortowania takiego zbioru w czasie O(nlogn) porównująca kąty nachylenia bez ich obliczania. Wymaga ona zdefiniowania funkcji alfa:
Niech:
pi (i=1..n) oznacza i-ty punkt w układzie współrzędnych
xi, yi oznaczają współrzędne punktu pi
wprowadźmy także wartość pomocniczą: di=|xi|+| yi|
wówczas funkcję alfa definiujemy:
alfa_i= \begin{cases} \frac{y_i}{d_i} & \text{ gdy } x_i \geq 0 \text{ oraz } y_i \geq 0\\ 2-\frac{y_i}{d_i} & \text{ gdy } x_i < 0 \text{ oraz } y_i \geq 0\\ 2+\frac{|y_i|}{d_i} & \text{ gdy } x_i < 0 \text{ oraz } y_i < 0\\ 4-\frac{|y_i|}{d_i} & \text{ gdy } x_i \geq 0 \text{ oraz } y_i < 0 \end{cases}
Można wykazać, że kąt nachylenia wektora wodzącego punktu pi jest mniejszy od kąta nachylenia wektora wodzącego punktu pj wtedy i tylko wtedy, gdy alfai jest niewiększe od alfaj. Jeśli dwa kilka punktów ma taki sam kąt, wówczas porządkujemy je wg najmniejszych wartości współrzędnej x.

Przykład:

a=(-5, -1), b=(4, -4), c=(2, 4), d=(-3, 2), e=(4, 1)
Image
Obliczamy wielkości pomocnicze:
da=6, db=8, dc=6, dd=5, de=5
Teraz można już wyznaczyć wartość funkcji alfa:
alfaa = 2 + |-1| / 6 = 2.1666
alfab=4 - |-4| / 8 = 3.5
alfac=4 / 6 = 0.6666
alfad=2 - 2 / 5 = 1.6
alfae=1/5=0.2
Po posortowaniu listy punktów wg współczynników alfa otrzymamy szukany ciąg punktów: e, c, d, a, b. Jak widać na rysunku, ciąg ten jest uporządkowany wg kątów wektorów wodzących (część prostej zaznaczonej na szaro ograniczony początkiem układu współrzędnych i punktem). Kąt jest mierzony między wektorem a osią X w kierunku matematycznym, czyli przeciwnym do ruchu wskazówek zegara.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał KnasieckiC/C++
.cpp
.cpp
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 28 sierpnia 2012 20:03
Komentarze
photo
-2 # asm 2009-10-03 21:51
"Jeśli dwa kilka punktów ma taki sam kąt, wówczas porządkujemy je wg najmniejszych wartości współrzędnej x".

trzeba pamietac, ze moga sie zdarzyc punkty o tym samym kacie nachylenia i tych samych wspolrzednych x (linia pionowa). Dlatego trzeba dodac porownywanie wspolrzednych y.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # e1dawca 2012-11-20 01:27
nie może się tak zdarzyć, że punkty będą miały ten sam kąt nachylenia oraz te same x bo to by oznaczało, że y też musi być taki sam.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-3 # Michał 2009-12-27 15:52
Jak mam użyć tego algorytmu żeby sortował względem danego punkty ?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Tomasz Lubiński 2010-01-05 18:50
Wystarczy współrzędne badanych punktów pomniejszyć o wartości współrzędnych punktu względem, którego chcesz sortować.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # foo 2010-02-11 20:57
Po co moduły w tej funkcji, jak już wiemy, jaki y_i ma znak?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Tomasz Lubiński 2010-02-13 15:01
A to dlatego, że wartość bezwględna brana jest z liczb ujemnych - potrzebna jest wartość bez znaku.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # eddick 2010-04-27 21:21
Mozna wiedziec co zmienic w kodzie aby punkty były sortowane wg zadanego wektora, a nie osi OX ? Przykładowo wczytuję punkty, a na końcu wczytuję wspolrzedne 2 punktow z ktorych składam wektor. Czy wówczas ta zasada przy tworzeniu ALFY może działać ?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-3 # wosiu 2011-12-02 01:49
Przeskalować wszystkie współrzędne tak, aby punkt według którego chcesz je posortować miał współrzędne (0,0).
czyli dla twojego punktu S:
for po wszystkich punktach P:
{
P.x-=S.x;
P.y-=S.y;
}
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz