Алгоритм Джарвиса(Метод заворачивания подарка)

Материал из Algocode wiki
Версия от 10:17, 26 февраля 2020; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Давайте выберем какую-то точку, которая гарантированно попадет в минимальную выпуклую оболочкуо, например обычно берут нижнюю и если таких несколько, то самую левую из них. Теперь давайте по одной набирать точки, как бы заворачивая нашу выпуклую оболочку(отсюда и название). Как же нам найти следующую точку в выпуклую оболочку, давайте пройдемся по точкам, которые мы еще не взяли в МВО и среди них выберем с минимальным полярным углом.

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

Асимптотика : для каждой точки выпуклой оболочки мы из всех оставшихся точек будем искать оптимальную - что будет работать за h(размер выпуклой оболочки) $\cdot n$

Важно помнить, что именно $O(hn)$, а не $O(n^2)$, так как существуют задачи на это.

 1 int base = 0;
 2 for (int i = 1; i < n; i++) {
 3     if (mas[i].y < mas[base].y) {
 4         base = i;
 5     }
 6     else if (mas[i].y == mas[base].y && mas[i].x < mas[base].x) {
 7         base = i;
 8     }
 9 }
10 convex_hull.push_back(base);
11 point first = mas[base];
12 point cur = first;
13 point prev = point(first.x - 1, first.y);
14 do {
15     double minCosAngle = 1e9; // чем больше угол, тем меньше его косинус
16     double maxLen = 1e9;
17     int next = -1;
18     for (int i = 0; i < n; i++) {
19         double curCosAngle = CosAngle(prev, cur, mas[i]);
20         if (Less(curCosAngle,minCosAngle)) {//если меньше сразу меняем
21             next = i;
22             minCosAngle = curCosAngle;
23             maxLen = dist(cur, mas[i]);
24         }
25         else if (Equal(curCosAngle, minCosAngle)) {// смотрим по длине
26             double curLen = dist(cur,mas[i]);
27             if (More(curLen,maxLen)) {
28                 next = i;
29                 maxLen = curLen;
30             }
31         }
32     }
33     prev = cur;
34     cur = mas[next];
35     convex_hull.push_back(next);
36 }
37 while (cur != first);



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

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