Algorytm Grahama
Algorytm Grahama to efektywny sposób na znalezienie otoczki wypukłej dla danego zbioru punktów w płaszczyźnie. Warto zaznaczyć, że nie ma jego wersji dla przestrzeni o wyższych wymiarach. Opracowany został przez Ronalda Grahama.
Jego czasowa złożoność obliczeniowa wynosi O(n log n).
Algorytm realizuje się według następujących kroków:
- Wybierz punkt (oznaczony jako O) z najniższą wartością współrzędnej y.
- Przesuń wszystkie punkty, aby punkt O zbiegał 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,
- odległości punktu Pi od początku układu współrzędnych.
- Wybierz punkt (oznaczony jako S) z najmniejszą współrzędną y; w przypadku, gdy kilka punktów ma tę samą wartość y, wybierz spośród nich ten z najmniejszą współrzędną x.
- Przeglądaj listę posortowanych punktów, zaczynając od punktu S:
- Od obecnej pozycji wybierz trzy kolejne punkty (oznaczone jako A, B, C).
- Jeżeli punkt B znajduje się na zewnątrz trójkąta AOC, może on należeć do otoczki wypukłej. Przejdź do następnego punktu na liście.
- Jeśli punkt B jest wewnątrz trójkąta AOC, nie należy on do otoczki. Usuń punkt B z listy i cofnij się o jedną pozycję (o ile bieżąca pozycja nie jest równa początkowej).
Ze względu na wcześniejsze kroki algorytmu (sortowanie oraz sposób wybierania analizowanych trójek punktów), dwa z trzech warunków przynależności punktu B do trójkąta AOC są spełnione, tj. B leży po „wewnętrznej” stronie prostych OA i OC. Aby stwierdzić przynależność do trójkąta, wystarczy zbadać, po której stronie odcinka AC znajduje się punkt B, wykorzystując znak iloczynu wektorowego:
|C – A| × |B – A|.
W praktyce można również zrealizować krok 4. jako krok 1, tj. przyjąć, że O = S.
Przykładowy przebieg algorytmu
W tej sekcji można przedstawić szczegółowy przebieg algorytmu z konkretnymi danymi wejściowymi.
Zobacz też
Przypisy
Bibliografia
Mark de Berg, Mirosław Kowaluk: Geometria obliczeniowa. Algorytmy i zastosowania. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007. ISBN 978-83-204-3244-2. Brak numerów stron w książce.
Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003, s. 263–267. ISBN 83-204-2796-7.
