Интересная задачка

ru_algorithms — 14.10.2010 Задачка для программистов:)

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

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

Оставить комментарий

Популярные посты:

• Архив