Поиск выпуклой оболочки методом грубой силы - EcsFlash/DataTypes GitHub Wiki

Множество точек на плоскости называется выпуклым если для любых двух точек p,q принадлежащих множеству, отрезок pq тоже принадлежит множеству. выпуклая оболочка множества из n точек - наименьший выпуклый многоугольник который содержит все точки множества внутри или на границе. TH - выпуклая оболочка любого множества S состоящего из n>2 точек не лежащих на одной прямой представляет собой выпуклый многоугольник с вершинами в некоторых точках S. Необходимо найти угловые точки множества S в порядке обхода по часовой или против часовой стрелки.

Алгоритм Грэхема — алгоритм построения выпуклой оболочки. Авсеева нам объясняла этот алгоритм так:

1. Берем самую левую тучку(p) в нашем пространстве и от нее за чем то проводим ось x(я так и не понял за каким хером мы это делали.ВОЗМОЖНО ДЛЯ ОПРЕДЕЛЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ ТОЧЕК...).
2. Сортируем оставшиеся точки по полярному углу относительно нашей выбранной точки.
3. Добавляем в стек самую первую из отсортированный точек.
4. Берем следующую по счету точку t. Пока t и две последних точки в текущей оболочке pi и pi−1 образуют правый поворот, удаляем оболочки pi.
5. Добавляем в стек(оболочку) t.
6. Повторяем 4 пункт пока не закончатся точки.

А теперь будет нормальное объяснение. Алгоритм Грэхема:

1. Находим точку p0 нашего множества с самой маленькой у-координатой (если таких несколько, берем самую правую из них), добавляем в ответ(стек).
2. Сортируем все остальные точки по полярному углу относительно p0.
3. Добавляем в ответ p1- самую первую из отсортированных точек.
4. Берем следующую по счету точку t. Пока t и две последних точки в текущей оболочке pi и pi−1 образуют левый поворот, удаляем оболочки pi.
5. Добавляем в стек(оболочку) t.
6. Повторяем 4 пункт пока не закончатся точки. Разница этих алгоритмов в том, что мы не делим наше пространство на 2 части(так мозг меньше тупит) и удаляем вершину из стека при разных поворотах(из за того, что мы берем самую нижнюю точку, а не самую левую)

Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки p последовательно убираем из оболочки точки с i+3-ей до i+1-ой

Псевдокод(авсеева нам вроде его не давала)

Graham(S)
  find i such that S[i] has the lowest y-coordinate and highest x-coordinate
  swap(S[i], S[1])
  sort S[2..n] by angle in relation to S[1]
  k = 2
  for p = 3..n
    while S[k - 1], S[k], S[p] has non-right orientation and k > 1
      k--
    swap(S[p], S[k + 1])  
    k++ 
  return k + 1

Graham(Q)
1) Пусть p0 — точка из множества Q с минимальной координатой y или самая левая из таких точек при наличии совпадений
2) Пусть <p1,p2,…,pm> — остальные точки множества Q, отсортированные в порядке возрастания полярного угла,
      измеряемого против часовой стрелки относительно точки p0
     (если полярные углы нескольких точек совпадают, то по расстоянию до точки p0)
3) Push(p0,S)
4) Push(p1,S)
5) for i = 2 to m do
6)     while угол, образованный точками NextToTop(S),Top(S) и pi, образуют не левый поворот
            (при движении по ломаной, образованной этими точками, мы движемся прямо или вправо)
7)       do Pop(S)
8)    Push(pi,S)
9) return S