Визуализация алгоритма Грэхема
Опубликовано 29 апреля, 2024 - 01:40 пользователем Верменич Михаил
Данная программа визуализирует алгоритм Грэхема.
В этом алгоритме перебираются все точки, после чего строится минимальная выпуклая оболочка (МВО).
Структура алгоритма:
-
Поиск краевой точек (так как она точно является одной из включаемых в оболочку). Здесь представлен
поиск точки с минимальным y и, если y одинаков у нескольких точек, минимальным x (В JS y=0 в самом верху). -
Далее происходит сортировка по полярному углу относительно начальной точки (для правильного порядка
перебора). -
После происходит перебор всех точек. Отбор включенных в МВО точек происходит по правилу правого поворота: если
при движении от одной точки к следующей поворот происходит вправо, то предыдущая точка исключается.
Скорость построения линий настраивается здесь (ms на линию):
// Скорость начальной отрисовки const startSpeed = 500;
В данную программу можно загружать свои точки, задавать количество и генерировать новые случайные точки.
Направление: