Как называется алгоритм / поле для позиционирования множества маленьких объектов для формирования фигур? - PullRequest
0 голосов
/ 03 июня 2011

извините, что английский не мой родной язык. Я хотел бы знать, как называется алгоритм / поле для позиционирования небольших объектов для формирования фигур?

Я не знаю, как он называется, поэтому приведу несколько примеров. e.g.1. В мультфильмах иногда встречается рой насекомых, образующих в воздухе скелетную голову

e.g.2. В войнах 1700-х годов пехотные отряды - это группа людей, стоящих вместе, образующих колонны или ряды, меняющих формы по мере продолжения битвы.

e.g.3 На церемониях открытия Олимпийских игр часто на площадке появляется группа танцоров, формирующих различные символы.

Таким образом, многочисленные маленькие объекты начинаются в произвольных положениях и перемещаются в новую позицию, так что они вместе образуют фигуру в 2D или 3D. Как называется такая техника?

Ответы [ 2 ]

1 голос
/ 03 июня 2011

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

0 голосов
/ 03 июня 2011

Если вы предполагаете, что танцоры / солдаты не мешают движению, то вы можете рассматривать проблему как проблему максимального соответствия.

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

Вы можете определить, возможно ли перейти из исходного состояния из начального состояния за время T, сформировав двудольный граф.Для каждого человека и конечной позиции, если человек может достичь позиции в <= T, добавьте грань человека в эту позицию.Затем запустите алгоритм максимального соответствия, чтобы увидеть, сможет ли каждый найти какую-то позицию в конечных точках в пределах ограничения по времени. </p>

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

http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs

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