Создаем полигон, используя numeric.js

Перевод статьи | Автор: Toby Schachman (спасибо!)

Проблемы вроде этих часто происходят при создании "UI игрушек" (которые подошли к Энди, в соответствии с твит-лентой). Найти аналитическое решение – интересная математическая задача, на самом деле, цель – просто получить работу реализации, чтобы Энди мог видеть это на экране и "почувствовать».

В этих ситуациях, вместо того чтобы писать страницы математике ищут закрытом виде раствора, я считаю, это альтернативная стратегия супер полезна: просто дайте компьютеру решить это за вас. Так как вы можете сформулировать проблемы автоматизации, вы можете попросить компьютер чтобы использовать численные методы, чтобы найти вам минимум.

Для этого вам просто нужно написать функцию (так называемую объективную), которая принимает некоторые параметры (количество степеней свободы в проблеме) и возвращает число (чтобы свести к минимуму). В этом случае, на вход – центр х и у многоугольника, угол, на который многоугольник поворачивается, а выход – радиус многоугольника, покрывающий все точки.

Затем, вы передаете свой целевую функцию и начальное предположение к алгоритму минимизации. Этот алгоритм использует некоторые формы градиентного спуска для итеративного возмущения начального предположения, пока не находит минимум. Выбор алгоритма минимизации не слишком важен. Я использую numeric.js uncmin, который я думаю, является js-версией некоторых Fortran алгоритмов из 80-х.

Обратите внимание, что это, как правило очень быстро работает на современных компьютерах.

Для более подробной информации, пожалуйста, сначала посмотрите мое решение (с аннотированным кодом) к более простой задаче нахождения окружности. Затем проверьте исходный код для этой страницы.

Н-угольник требует дополнительной тригонометрии, которая немного сложна, но полностью послушной, в отличие от аналитического решения этой проблемы. Это остается в качестве упражнения для читателя, но вот вариант, который я использовал (буквы упоминаются в исходном коде для этой страницы).

Полигон немного сложнее, чем круг, потому что вы можете застрять в локальном минимуме, если угол "застрял". Алгоритмы градиента спуска найдут только локальный минимум, а не глобальный минимум. Они "скатятся с холма", пока они не найдут плоскую часть, но может быть еще ниже плоских деталей в областях пространства параметров. Для круга имеется только один локальный минимум, глобальный минимум, поэтому алгоритм всегда находит их без помех. Но поскольку проблема в том, что многоугольник имеет локальные минимумы, я запускаю алгоритм минимизации 20 раз со случайными начальными догадками и принимаю лучший результат. Это, похоже, работает, но может быть скорректировано в зависимости от компромиссов приложения.