Algorytm Grahama

Z Wikipedii

Algorytm Grahama to efektywny algorytm wyszukiwania otoczki wypukłej skończonego zbioru punktów płaszczyzny; czasowa złożność obliczeniowa: O(n lgn).

Algorytm przedstawia się następująco:

1. Wybierz dowolny punkt (ozn. O) należący do otoczki wypukłej punktów (najczęściej jest to centroid).
2. Przesuń wszystkie punkty tak, by punkt O pokrył się z początkiem układu współrzędnych.
3. Posortuj punkty leksykograficznie względem: kąta pomiędzy wektorem OP_i a dodatnią osią układu współrzędnych, oraz odległości punktu P_i od początku układu współrzędnych.
4. 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 nich punkt o najmniejszej współrzędnej x.
5. 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).

Ze względu na wcześniejsze kroki algorytmu (sortowanie i sposób wybierania analizowanych trójek punktów) dwa z trzech warunków należenia punktu B do trójkąta AOC są spełnione (B leży po "wewnętrznej" względem trójkąta stronie prostych OA i OC), więc do stwierdzenia przynależności do trójkąta wystarczy zbadać, po której stronie odcinka AC znaduje się punkt B. W tym celu bada się znak iloczynu wektorowego .

 To jest tylko zalążek artykułu związanego z matematyką i informatyką. Jeśli możesz, rozbuduj go.