Визуализация алгоритма Грэхема

Данная программа визуализирует алгоритм Грэхема.

В этом алгоритме перебираются все точки, после чего строится минимальная выпуклая оболочка (МВО).

Структура алгоритма:

  • Поиск краевой точек (так как она точно является одной из включаемых в оболочку). Здесь представлен
    поиск точки с минимальным y и, если y одинаков у нескольких точек, минимальным x (В JS y=0 в самом верху).
  • Далее происходит сортировка по полярному углу относительно начальной точки (для правильного порядка
    перебора).
  • После происходит перебор всех точек. Отбор включенных в МВО точек происходит по правилу правого поворота: если
    при движении от одной точки к следующей поворот происходит вправо, то предыдущая точка исключается.

Скорость построения линий настраивается здесь (ms на линию):

// Скорость начальной отрисовки
const startSpeed = 500;

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