Выпуклая оболочка: обтянем точки резинкой

29 подписчиков

12+
12+

1 просмотр

2 дня назад

ПожаловатьсяНарушение авторских прав

29 подписчиков

12+
12+

1 просмотр

2 дня назад

ПожаловатьсяНарушение авторских прав
12+
12+

1 просмотр

2 дня назад

Статья и интерактив: https://grundyjs.ru/r/convex-hull/ Как найти внешнюю границу набора точек? Представим натянутую вокруг них резинку: она охватывает весь набор и держится за крайние точки. Эта граница вместе с областью внутри — выпуклая оболочка. Разбираем алгоритм Эндрю: упорядочиваем точки слева направо, строим нижнюю и верхнюю цепочки, затем соединяем их. Для проверки берём две последние точки цепочки и следующую точку набора. Если путь через них поворачивает вправо или все три лежат на одной прямой, убираем из текущей цепочки вторую точку тройки. Повторяем проверку перед добавлением новой точки. Точка, убранная из нижней цепочки, может войти в верхнюю — из набора она не удаляется. Перемещаем внутреннюю точку за границу и наблюдаем изменение оболочки. Если все точки лежат на одной прямой, результат — отрезок между двумя крайними. В статье можно двигать, добавлять и удалять точки, выбирать готовые примеры и разбирать построение по шагам. После редактирования остаётся готовая оболочка; для пошагового разбора нажмите «Сначала», затем «Старт». Есть ссылка на свой пример и экспорт анимации. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #выпуклаяОболочка #алгоритмЭндрю #геометрия #алгоритмы #ConvexHull

Название:

Выпуклая оболочка: обтянем точки резинкой

Категория:

Обучение