Algorytm Grahama
Z Wikipedii
Algorytm Grahama to efektywny algorytm wyszukiwania otoczki wypukłej zbioru punktów płaszczyzny; czasowa złożność obliczeniowa: O(n lgn).
Algorytm przedstawia się następująco:
- Wybierz dowolny punkt (ozn. O) leżący wewnątrz otoczki wypukłej punktów (najczęściej jest to centroid).
- Przesuń wszystkie punkty tak, by punkt O pokrył się z początkiem układu współrzędnych.
- Posortuj punkty leksykograficznie względem: kąta pomiędzy wektorem OPi a dodatnią osią układu współrzędnych, oraz odległości punktu Pi od początku układu współrzędnych.
- Wybierz punkt (ozn. S) o najmniejszej współrzędnej y; jeśli kilka punktów ma tę samą współrzędną y, to wybierz spośród niech punkt o najmniejszej współrzędnej x.
- Przeglądaj listę posortowanych punktów poczynając od punktu S:
- Od bieżącej pozycji weź trzy kolejne punkty (ozn. A, B, C).
- Jeśli punkt B leży na zewnątrz trójkąta AOC, to należy do otoczki wypukłej. Przejdź do następnego punktu na liście.
- Jeśli punkt B leży wewnątrz trójkąta AOC, to znaczy, że punkt ten nie należy do otoczki. Usuń punkt B z listy i cofnij się o jedną pozycję (o ile bieżąca pozycja jest różna od początkowej).
W praktyce nie testuje się przynależności do trójkąta, wystarczy stwierdzić po której stronie odcinka AC znaduje się punkt B - w tym celu bada się znak iloczynu wektorowego .