Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе

в 10:07, , рубрики: Алгоритмы, математика, математические этюды, метки: ,

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

Теорема Кемпе

С развитием техники и появлением поездов у пытливых умов встала очень интересная проблема, а можно ли создать шарнирный механизм, который переводит круговое движение, в движение по прямой, выражаясь по-другому, рисует прямую. Шарнирный механизм — это много скрепленных между собой палочек, которые могут свободно вращаться в точках креплений. Многие ученые бились над этой проблемой, придумывая хитроумные механизмы, но все они рисовали неточные прямые. Вот, например, механизмы Ватта, Чебышева и Хойкена:

Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе

Многие математики считали, что проблема создания шарнирного механизма, рисующего идеальную прямую линию, является в принципе неразрешимой, пока в середине 19-го века не был открыт гениальный механизм Липкина-Посселье, который рисует точную прямую:
Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе
В этом механизме все палочки одинакового цвета имеют одинаковую длину. Доказать, что механизм действительно рисует прямую можно прямыми выкладками, как говорится, в лоб. Но люди, знакомые с преобразованием инверсии могут увидеть довольно четкую логику в доказательстве. К моменту изобретения механизма Липкина-Посселье уже смазочные материалы были настолько хороши, что в технике могли обходиться без этого идеального преобразователя в прямолинейное движение. Ведь можно через еще одну палочку передавать почти прямолинейное движение на поршень. Эта палочка не будет всегда идеально параллельной направляющей поршня, но в этом ничего страшного нет. В итоге механизм Липкина-Посселье так и не нашел широкого применения в технике, но зато оказал огромное влияние на математику.
Через несколько лет математик-адвокат Кемпе приводит алгоритм, как абсолютно для любой алгебраической кривой на плоскости построить шарнирный механизм, который умеет рисовать только эту кривую и больше ничего не умеет. Иными словами, существует механизм, ограниченный в движении одной степенью свободы. Двигаясь вдоль этой степени свободы механизм рисует нашу алгебраическую кривую. Прекрасное изложение доказательства Кемпе я нашел в этой статье. Напомним читателю, что алгебраические кривые, о которых идет речь в теореме Кемпе — это кривые заданные уравнением Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе, где Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе — любой многочлен. Например, Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе — это окружность радиуса Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе, Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе — наклоненная прямая, Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе — парабола. В своем доказательстве Кемпе использует много интересных идей, но ключевым инструментом построения является уже известный нам механизм Липкина-Посселье.

Процесс

Как только я узнал о теореме Кемпе, я сразу же захотел написать программу, в которой пользователь может нарисовать любую кривую, скажем свою подпись, а программа аппроксимирует подпись алгебраической кривой, а потом по алгоритму Кемпе построит шарнирный механизм, подделывающий ее. Мне очень хотелось сделать веб-приложение, чтобы пользователю не нужно было ничего устанавливать на компьютер, чтобы можно было зайти на сайт и запустить все «в один клик». Так как я не программист, то это еще было для меня прекрасной возможностью познакомиться с JavaScript и HTML5.
После того, как я выучил доказательство Кемпе, передо мной встала очень серьезная проблема:
как аппроксимировать подпись алгебраической кривой Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе с хорошей точностью, быстро, да еще и на медленном JavaScript? Существует очень простой, но не подходящий нам, способ аппроксимации кривой объединением маленьких окружностей, разбросанных вдоль кривой, как, показано на картинке:
Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе
Каждая маленькая Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе-ая окружность является, очевидно, алгебраической кривой, так как задается полиномиальным уравнением Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе, где Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе — центр окружности, а Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе — ее радиус. Алгебраической кривой, очевидно, будет и объединение всех маленьких окружностей, так как это объединение будет задаваться полиномиальным уравнением Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе. Но как вы видите, такой вид аппроксимации нам совершенно не подходит, потому что возникает очень много точек самопересечений. Хотелось бы иметь более «красивую» аппроксимацию. Оказывается, проблема «красивой» аппроксимации сложная как с математической точки зрения, так и с вычислительной. Чтобы как-то прочувствовать это, полезно представить алгебраическую кривую Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе как пересечение поверхности Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе и плоскости Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе. Линия пересечения очень чувствительна к коэффициентам многочлена Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе, она совершенно неконтролируемо может быть несвязной, иметь точки ответвлений, что и будет портить «красоту» аппроксимации.
После недели экспериментов с различными алгоритмами, все мои попытки хоть как-то аппроксимировать кривую оказались тщетными. Все алгоритмы работали очень медленно и плохо. Я почти сдался, предварительно запостив вопрос на mathoverflow, где традиционно сидит много профессиональных математиков. В вопросе я вскользь упомянул, что мне это нужно для того, чтобы подделывать подписи шарнирами. Каково было моё удивление, что через день-два мне ответил математик Михаил Капович. Ответил «не в бровь, а в глаз». Как оказалось, он когда-то занимался теоремой Кемпе и вместе с Джоном Миллсоном в своей статье доказал, что можно построить шарнирные механизмы не только для алгебраических кривых, но и для кривых, которые более естественно подходят для задач аппроксимаций, а именно, для кривых, заданных параметрически полиномиальными кривыми: Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе. К примеру, Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе. Такими кривыми проще простого аппроксимировать любые непрерывные кривые, в том числе и нашу подпись. Можно аппроксимировать так называемыми полиномами Чебышева, а можно сначала приблизить рядами Фурье, а потом тригонометрические функции в рядах Фурье приблизить рядами Тейлора. Получается, что вместо того, чтобы пытаться аппроксимировать кривую алгебраическими кривыми, лучше изменить само доказательство Кемпе и научиться строить шарнирные механизмы, умеющие строить более подходящие для задач аппроксимации кривые.
Вся эта история по ощущениям была похожа на находку огромного алмаза. Но, к своему стыду, я не до конца разобрался в той статье. Статья написана довольно сложно. Но сам факт того, что существует решение моей проблемы открыл мне глаза. Я сообразил, что незначительным изменением оригинального доказательства Кемпе можно строить шарниры, рисующие косинусоидальные тригонометрические кривые, то есть кривые вида Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе. Такими кривыми даже еще легче аппроксимировать нашу подпись (теория рядов Фурье), чем кривыми со статьи Каповича-Миллсона. Действительно, из теории рядов Фурье следует что на отрезке Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе функции Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе и Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе можно разложить в ряд по косинусам. Для точности аппроксимации Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе имеем:
Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе
Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе
Коэффициенты Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе и Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе легко находятся. Нужно просто умножить равенства слева и справа на Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе и проинтегрировать от Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе до Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе, тогда в правой части почти все интегралы обнулятся, кроме одного при члене Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе. В итоге получится:
Подделываем вашу подпись при помощи шарнирного механизма. Теорема Кемпе
Я очень долго думал размещать ли в этом посте алгоритм построения шарнира, который и строит эти тригонометрические кривые. Потом я понял, что это добавит математической скучности в текст. Люди обычно не любят в текстах такого рода читать длинные доказательства. Поэтому я обойдусь просто ссылкой. Любопытные могут посмотреть.
A вот, собственно, и само приложение, которое подделывает вашу подпись: david.wf/linkage. Прошу заметить, мышкой можно двигать конструкцию, а скроллером — приближать и удалять. Приложение работает на современных браузерах, на старых я не тестировал. Меньше всего тормозит на хроме, так как только хром намного быстрее других браузеров рисует прямые (пруфлинк). Признаться, я потратил много сил на оптимизацию, чтобы ничего не тормозило на слабых компах, но, скажу честно, особых успехов не достиг. Еще раз подчеркну, шарнир, который строит программа ничего не умеет рисовать, кроме вашей подписи. Шарнир приводится в движение крутящимся синеньким треугольником — «двигателем».

Автор: khdavid

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js