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

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

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

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

Многие математики считали, что проблема создания шарнирного механизма, рисующего идеальную прямую линию, является в принципе неразрешимой, пока в середине 19-го века не был открыт гениальный механизм Липкина-Посселье, который рисует точную прямую:

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

Процесс

Как только я узнал о теореме Кемпе, я сразу же захотел написать программу, в которой пользователь может нарисовать любую кривую, скажем свою подпись, а программа аппроксимирует подпись алгебраической кривой, а потом по алгоритму Кемпе построит шарнирный механизм, подделывающий ее. Мне очень хотелось сделать веб-приложение, чтобы пользователю не нужно было ничего устанавливать на компьютер, чтобы можно было зайти на сайт и запустить все «в один клик». Так как я не программист, то это еще было для меня прекрасной возможностью познакомиться с JavaScript и HTML5.
После того, как я выучил доказательство Кемпе, передо мной встала очень серьезная проблема:
как аппроксимировать подпись алгебраической кривой с хорошей точностью, быстро, да еще и на медленном JavaScript? Существует очень простой, но не подходящий нам, способ аппроксимации кривой объединением маленьких окружностей, разбросанных вдоль кривой, как, показано на картинке:

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


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

Я очень долго думал размещать ли в этом посте алгоритм построения шарнира, который и строит эти тригонометрические кривые. Потом я понял, что это добавит математической скучности в текст. Люди обычно не любят в текстах такого рода читать длинные доказательства. Поэтому я обойдусь просто ссылкой. Любопытные могут посмотреть.
A вот, собственно, и само приложение, которое подделывает вашу подпись: david.wf/linkage. Прошу заметить, мышкой можно двигать конструкцию, а скроллером — приближать и удалять. Приложение работает на современных браузерах, на старых я не тестировал. Меньше всего тормозит на хроме, так как только хром намного быстрее других браузеров рисует прямые (пруфлинк). Признаться, я потратил много сил на оптимизацию, чтобы ничего не тормозило на слабых компах, но, скажу честно, особых успехов не достиг. Еще раз подчеркну, шарнир, который строит программа ничего не умеет рисовать, кроме вашей подписи. Шарнир приводится в движение крутящимся синеньким треугольником — «двигателем».