?

Log in

No account? Create an account

rauf


Блог Алиева Рауфа

О жизни и о себе


Previous Entry Поделиться Next Entry
Интересная задачка
rauf
Задачка для программистов:)

Сейчас у меня проект один назревает, приложение под айфон. В рамках него есть задачка: распределить N прямоугольничков фиксированной высоты, но переменной ширины внутри области X на Y пикселей. Ее можно решить в лоб (как и решено сейчас)— прямоугольнички просто случайно распределяются по области, так, чтобы помещаться обоими краями (если это возможно). Поскольку генератор случайных чисел иногда преподносит сюрпризы, мы имеем иногда прямоугольники, наезжающие друг друга настолько, что некоторых и не видно, при этом какой-нибудь угол области практически не занят. Назревает вопрос: как можно распределить их таким образом, чтобы наложения были минимальны? Есть несколько решений, сразу приходящих на ум: например, ставить их последовательно и принимать выдаваемые генератором случайных чисел координаты только тогда, когда с учетом ширины и высоты блока он ни на кого не "наползает", а после 100 неудачных попыток принимать первые попавшиеся координаты и переходить к следующему блоку. Алгоритм плохой, но явно лучше, чем описанный в самом начале. Но явно хуже, чем мог бы быть. Например, хорошо было бы равномерно распределять блоки. То есть, два блока должны каждый раз находиться в разных местах, но примерно равноудаленно друг от друга и от центра, а не в одном каком-нибудь углу.

Посему принимаются идеи, как сделать лучше? У меня самого уже несколько есть. Ау, программисты :-) Ну как, хорошая задачка?


  • 1
Хмм... может такой вариант?
на область рандомно устаналивается один блок. После этого по центру блока ставится точка через которую проводятся вируальные линии, которые создают еще 4 области в каждую из областей рандомно ставится еще по одному блоку и также в центре каждого блока создается точка через которю "проводятся" линии, которе создают еще области.
таким образом можно вполне равномерно занять основную область блоками.
причем при заполнении можно учитывать такие параметры как высота и щирина облоасти в которую должен быть помещен блок таким образом чтобы широкие блоки не попадали в "узкие" области, а также например допуски по наезжанию блоков на соседние области.

не будет равномерного распределения.. сейчас покажу, что я придумал

(Deleted comment)
все-таки кажется это немножко иное.
Мне нужно расбросать блоки так, чтобы наползание друг на друга было минимальным (но оно допустимо, если больше девать некуда), и чтобы распределение было равномерным.

Равномерное рапределение чего по чему?

  • 1