Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Хаотичное позиционирование элементов

Автор: japanes 6.3.2008, 01:41

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

Автор: ksnk 6.3.2008, 11:37

Я бы не назвал конструкцию на картинке хаотичной smile

Можно предложить такой алгоритм. Есть массив div'ов с определенными размерами.
- первый элемент выставляем в центр композиции.
Каждый следующий выставляем в ЦЕНТР композиции и выбираем для него вектор (случайно). Если пересечение с предыдущими элементами есть - смещаем элемент по вектору на случайное, но не очень большое число.
Эффективно определить пересекаются ли прямоугольники не просто. Можно тупо пребирать все уже размещенные, и сравнивать габариты, а можно представить всю композицию как большой 2-х мерный массив (каждый элемент которого изображает квадрат 10х10). при установке элемента нужно отметить соответствующие элементы массива как занятые (Этакий "морской бой").

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

Автор: maxdiver 7.3.2008, 19:56

Есть идея простая:

Код

for (int i=0; i<n; ++i) {
    while (true) {
        double x = (rand() % 10000) * 0.001,  y = (rand() % 10000) * 0.001; // короче, рандомные :)
        bool good = true;
        for (int j=0; j<i && good; ++j)
           good &= !intersect (figure[i], figure[j]); // предполагая, что j в позиции ans_x[j], ans_y[j], а i в позиции x, y
        if (good) {
           ans_x[i] = x;
           ans_y[i] = y;
           break;
        }
    }
}

Есть предположение, что такая весчь найдёт ответ, если конечно тест не слишком плотный. Можно её оформить как перебор с возвратом, чтобы выбор позиции первой фигуры не мог оказаться фатальным.

Автор: japanes 9.3.2008, 02:35

с С++ не совсем знаком, а именно строка:

Код


good &= !intersect (figure[i], figure[j]);

вызвала вопрос о том, что она делает :-/

Автор: maxdiver 9.3.2008, 15:08

japanes
это значит:

Код

if (!intersect (figure[i], figure[j]))
   good = false;

P.S. а я подумал, что на псевдокоде C++ понятнее будет smile

Автор: japanes 9.3.2008, 16:08

а intersect() что за функция, чего делает?

P.S. на javascript-е было бы в самый раз ;)

Автор: maxdiver 10.3.2008, 15:21

intersect - проверяет, пересекаются два блока или нет (если один принадлежит другому, то это считается как пересечение).
Эту функцию нужно, конечно, реализовать самому, но её реализация - это особая тема smile

Автор: japanes 10.3.2008, 17:01

maxdiver, на самом деле весь вопрос с реализацией построения блоков уперся именно в эту функцию... может через аську решим ? 339-541-633