Равномерная расстановка точек в произвольной фигуре

[Hauts]

Всем привет, с наступающим!

В общем, задумал я одну демку сделать. Смысл такой — есть последовательность кадров, черно-белых. В каждом кадре нарисовано пятно. При воспроизведении видно, как форма пятна "трансформируется". Далее я хочу расставить поверх пятна в каждом кадре некоторое фиксированное количество точек (предположим сто) таким образом, чтобы они равномерно заполнили площадь фигуры (пятна). На следующем кадре мне необходимо сделать то же самое, но с учетом того, чтобы соответствующие точки переместились в соответствующее место нового пятна. Грубо говоря, чтобы точка номер 45 не прыгала с одного угла пятна на другое при небольшом изменении формы пятна.

Пока что я вижу решение задачи таким: смотрим габариты пятна в текущем кадре, получаем прямоугольную область. Рассчитав размер точки исходя из площади пятна (делим площадь габаритной области на количество точек — получаем площадь габаритов для точки), мы располагаем точки во всегда одинаковом порядке — слева направо, сверху вниз. На этом момента получаются уже не точки даже, а полноценные окружности. Далее включаем механизм столкновения точек между собой и ограничения по форме пятна. То есть для столкновения между собой довольно тривиальный механизм будет использован, а вот для constrain по форме пятна уже придется шаманить с битмапдатами. И прогоняем такой код раз 200, например.

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

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

Есть у кого-нибудь идеи по этому поводу? Я больше чем уверен, что такая задача не нова и наверняка есть какие-нибудь более лаконичные и разумные решения.

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

[-De-]

Сделать, что точки отталкиваются друг от друга + ограничение на "не вылазят за фигуру" (если при смене форме какие-то вылезли, то вернуть в ближайшую точку фигуры). Отталкивание сделать пропорционально расстоянию. И по-моему самое сложное это именно возврат точки в фигуру, я бы попробовал написать остальную "физику", если была бы функция "вернуть вылезшую точку в фигуру".

[DaFive]

О: http://www.flasher.ru/forum/blog.php?b=613
Не?

[Hauts]

Сообщение от DaFive

О: http://www.flasher.ru/forum/blog.php?b=613
Не?

Нет конечно

[nuToH]

если есть мат.форма "пятна" то отталкивать точки от рёбер можно проецируя каждую точку на каждое ребро ( DOT ), и уже от ближайшей точки на ребре до нашей точки отталкивать обратнО пропорционально расстоянию. если нет границ пятна, то можно попытаться поиграться с притяжением точек в центр в зависимости от угла( относительно центра), например -

angle = Math.atan2 (point.y, point.x)
point.x -= Math.cos (angle) * point.length / state_x;
point.y -= Math.sin (angle) * point.length / state_y;

меняя state_x и state_y получил вот такую хрень:

Untitled-1.swf   (1.8 Кб)

[Hauts]

Спасибо за ответы, буду пробовать.

Пока что получилось вот так:

fill_image_with_points.swf   (12.0 Кб)

Проверял идентичность результатов с помощью принтскрина и пэйнта, — вроде всегда встают в одно и то же положение.

[Zebestov]

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

[Tails]

Hauts,
Сколько примерно итераций?

[Hauts]

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

[Hauts]

Другой тест показывает, что соответственное перемещение не получится с моим подходом.

Хм, даже и не знаю, как это решить.

fill_image_with_points_2.swf   (12.4 Кб)