Алгоритм Грэхема

Материал из Algocode wiki
Перейти к: навигация, поиск

Алгоритм Грэхема базируется на следующей идее: Давайте не искать следующую точку каждый раз, а сделаем так, чтобы у нас всегда была оптимальная точка и мы могли бы просто ее достать и проверить.

В прошлом алгоритме мы искали точку, оптимальную по полярному углу, тогда давайте сейчас сразу отсортируем точки по полярному углу и сразу возьмем две первые точки в МВО.

Теперь будем делать следующий алгоритм, пока все точки не будут просмотрены :

1) Возьмем первую из отсортированных точек.

2) Проверем последние три точки из взятых, если они образуют правый поворот, то удалим предпоследнюю точку

Сделать это можно, например, стеком. Код есть ниже.

Асимптотика : Мы просмотрим одну точку и либо удалим ее, либо оставим, то есть сам поиск МВО работает за линейное время, но мы еще делаем сортировку, а $\rightarrow$ алгоритм работает за $O(n\log(n))$, при этом его корректность вытекает из предыдущего алгоритма.

Красивая визуализация - https://visualgo.net/en/convexhull

красивое видео - https://www.youtube.com/watch?v=BTgjXwhoMuI

 1 struct Point {
 2     int x, y;
 3 };
 4 
 5 Point operator -(Point a, Point b)
 6 {
 7     return {a.x - b.x, a.y - b.y};
 8 }
 9 
10 int operator * (Point a, Point b)
11 {
12     return a.x * b.x + b.y * a.y;
13 }
14 
15 int operator ^(Point a, Point b)
16 {
17     return a.x * b.y - b.x * a.y;
18 }
19 
20 bool cw(Point a, Point b, Point c)
21 {
22     return (a - b) * (c - b) > 0;
23 }
24 
25 bool ccw(Point a, Point b, Point c)
26 {
27     return (a - b) * (c - b) < 0;
28 }
29 
30 int main()
31 {
32     sort(all(p2), comp);
33     vector<Point> s;
34     s.push_back(p[min_ind]);
35     for (int i = 0; i < n - 1; i++) {
36         if (p2[i].x == s[s.size() - 1].x && p2[i].y == s[s.size() - 1].y)
37             continue;
38         while (s.size() > 1 && (vect(s[s.size() - 1], s[s.size() - 2]) ^
39                vect(s[s.size() - 1], p2[i])) > 0)
40             s.pop_back();
41         s.push_back(p2[i]);
42     }
43 }



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin