Algorytm Grahama

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Algorytm Grahama
Rodzaj znajdowanie otoczki wypukłej
Złożoność
Czasowa O(n \log n)

Algorytm Grahama to efektywny algorytm wyszukiwania otoczki wypukłej skończonego zbioru punktów płaszczyzny; nie istnieją warianty dla przestrzeni o wyższych wymiarach. Pomysłodawcą algorytmu jest Ronald Graham[1].

Czasowa złożoność obliczeniowa wynosi O(n \log n).

Algorytm przebiega następująco:

  1. Wybierz dowolny punkt (ozn. O) należący do otoczki wypukłej punktów.
  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,
    • 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, wybierz spośród nich ten 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 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, tj. B leży po "wewnętrznej" względem trójkąta stronie prostych OA i OC. Zatem do stwierdzenia przynależności do trójkąta wystarczy zbadać, po której stronie odcinka AC znajduje się punkt B, w tym celu wykorzystuje się znak iloczynu wektorowego |C-A| \times |B-A|.

W praktyce można również utożsamić krok 4. z 1., tzn. przyjąć, że O = S.

Przypisy

  1. Ronald Graham. An efficient algorithm for determining the convex hull of a finite planar set. „Information Processing Letters”. 1, s. 132-133, 1972 (ang.). 

Bibliografia[edytuj | edytuj kod]

  • Mark de Berg, Mirosław Kowaluk: Geometria obliczeniowa : algorytmy i zastosowania. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007. ISBN 978-83-204-3244-2.
  • Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003, s. 263-267. ISBN 83-204-2796-7.

Zobacz też[edytuj | edytuj kod]