Алгоритм преобразования одной фигуры в другую.

Я пытаюсь работать над алгоритмом, который превратит одну "форму" в другую "форму". Обе формы произвольны и могут даже иметь более мелкие, несвязанные формы.

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

Вот иллюстрация:

Я просто не знаю, с чего начать. Образ выше - упрощение, фактический прецедент имеет более сложные формы/контуры. Моя основная проблема: как обрабатывать непересекающиеся фигуры? Лучшее, что я могу придумать, - это выяснить ближайшую точку между двумя частями и объединить их вместе как часть пути. Но как мне это реализовать?

У меня пока нет кода, я все еще на стадии планирования. Я предполагаю, что я прошу, может ли кто-нибудь связать меня с любыми ресурсами, которые могут помочь, или дать какие-либо указатели. Поиск Google дал некоторые интересные алгоритмы морфинга, но все они имеют дело с полными изображениями и включают разбиение изображения на части, чтобы изменить их, что не то, что я ищу.

Обратите внимание, что это будет использоваться в JavaScript, но может быть предварительно вычислено в PHP, если это проще.

Ответ 1

Я нашел демонстрацию (используя Raphael.js) морфинга и анимации движения в JavaScript, показывая, как Raphael.js может используется для превращения одной кривой в другую кривую.

Кроме того, этот связанный вопрос (о анимации формы в JavaScript) может содержать некоторые ответы, имеющие отношение к этому вопросу.

библиотека MorpherJS также может быть подходящей для этой цели. Некоторые демонстрации схемы морфинга с MorpherJS можно найти здесь.

Ответ 2

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

Сначала нам нужно выяснить, какой пиксель в файле from_shape попадает на какой пиксель в to_shape.
Мы можем понять это следующим образом:

Поместите to_shape поверх from_shape.
Для каждого пикселя в from_shape найдите его ближайший пиксель to_shape.
Каждый пиксель в форме должен иметь уникальный идентификатор, этот идентификатор может быть, например, его местоположением xy.
Теперь вы можете записывать каждый уникальный пиксель в формате from_shape и какой уникальный пиксель он переходит в to_shape.
Удалите перекрывающиеся фигуры и вернитесь к исходным,
только теперь каждый пиксель в from_shape знает свое назначение в to_shape.

Нам также нужно знать, какие "братья и сестры" имеют каждый пиксель.
Братство - это пиксель, который находится рядом с другим пикселем.
Чтобы найти его, перейдите к заданному пикселю, соберите все пиксели в радиусе один от него, все из которых являются черными.. являются отпиксельными братьями и сестрами. Эта информация необходима, чтобы сохранить форму как единое целое, когда пиксели перемещаются к месту назначения. Пропуск братьев и сестер существенно ускорит и упростит морфинг, но без них форма может стать фрагментированной во время морфинга. Можете начать с версии без брака, посмотрите, как это происходит.

И, наконец, мы реализуем морф:

Существует файл morph_time_duration.
Для каждого пикселя from_shape найдите расстояние до места назначения в to_shape.
Это расстояние, деленное на morph_time_duration, является скоростью пикселя во время морфинга.
Кроме того, угол к месту назначения - это угол для перемещения.
Итак, теперь у вас есть скорость и угол.
Итак, каждый кадр в процедуре морфинга, данный from_pixel теперь знает, в каком направлении двигаться, скорость, и он также знает своих братьев и сестер. Поэтому в каждом кадре просто нарисовать пиксель в новом месте, пройдя его скорость в своем направлении. А затем нарисуйте линию для всех этих братьев-сиблиров.

И это отобразит ваш морф.

Ответ 3

Делать это не очень легко, но я могу дать вам пару отправных точек. Если вам нужна простая реализация javascript, отличная отправная точка: http://raphaeljs.com/animation.html который делает именно то, что вы хотите. Таким образом, вы можете проверить, какие методы вызывают, и просмотреть источник библиотеки для этих методов, чтобы увидеть реализацию.

Если вам нужно преобразовать 2 изображения в PHP, я бы предложил вам использовать какое-то расширение и не делать этого в простом PHP. Вот пример использования ImageMagick для этого: http://www.fmwconcepts.com/imagemagick/shapemorph2/index.php

Если вы хотите узнать больше о его внутренних функциях: http://web.mit.edu/manoli/www/ecimorph/ecimorph.html#algo

Надеюсь, что это поможет.

Ответ 4

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

Если вы просто ищете логический подход, здесь, где я бы начал (не проделав математику годами и не изучив внутреннюю работу связанных графических библиотек):

Выберите расстояние, измеряемое в любых единицах, имеющее смысл, возможно, пиксели.
Определите каждый непрерывный край в каждой форме. Выберите произвольную точку на одном ребре для каждой фигуры (скажем, на плоскости, где (0,0) представляет верхний левый угол, краевую точку на каждой фигуре, ближайшей к (0,0)), и выровняйте отдельные фигуры на этой точка. Для целей вашего преобразования эта точка останется неподвижной, и все остальные точки будут соответствовать ей.
Если ваша фигура имеет два или более отдельных края, закажите их по длине периметра. Рассмотрим более короткие длины, которые будут подчинены более длинным длинам. Используйте аналогичный процесс, как на шаге 2, чтобы выбрать произвольную точку для соединения этих двух ребер.
В каждой из выбранных вами точек подсчитывайте точки вокруг своих ребер в интервале расстояния, выбранного на шаге 1.
(слева как упражнение для читателя) согласовывайте свои точки на ваших разрозненных ребрах вместе и в целевую форму, выравнивая, уменьшая или добавляя точки по краям по мере необходимости.

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

Просто бросая некоторые идеи, я не знаю, насколько глубоко проблема.